Logo
All Random Solved Random Open
OPEN
Every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint paths.
A problem of Erdős and Gallai. Lovász [Lo68] proved that every graph on $n$ vertices can be partitioned into at most $\lfloor n/2\rfloor$ edge-disjoint paths and cycles. Chung [Ch78] proved that every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint trees. Pyber [Py96] has shown that every connected graph on $n$ vertices can be covered by at mst $n/2+O(n^{3/4})$ paths.

Hajos [Lo68] has conjectured that if $G$ has all degrees even then $G$ can be partitioned into at most $\lfloor n/2\rfloor$ edge-disjoint cycles.

See also [184] and the entry in the graphs problem collection.