The Decomposition of Graphs into a Finite Number of Paths
Bruce L. Rothschild · Canadian Journal of Mathematics · 1965
In (3) Ore poses two problems concerning the decomposition of graphs into edge-disjoint paths. The first is to find the conditions on a graph so that it can be decomposed into a finite number k of edge-disjoint, two-way infinite paths and no fewer. In (2) Nash-Williams solves this problem. The results of (2) are used here to solve the second problem, to find conditions on a graph so that it can be decomposed into a finite number k of edge-disjoint paths (finite, one-way infinite, and two-way infinite) and no fewer.