Problem #583: Every connected graph on $n$ vertices can be partitioned...

---

Progress

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, which implies that every graph can be partitioned into at most $n-1$ paths.

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 most $n/2+O(n^{3/4})$ paths.

If we drop the edge-disjoint condition then this conjecture was proved by Fan [Fa02].

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] for an analogous problem decomposing into edges and cycles and [1017] for decomposing into complete graphs. See also the entry in the graphs problem collection.