We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $leftlceil frac{n}{2}rightrceil$ paths, while a conjecture of Haj{o}s states that any Eulerian graph on $n$ vertices can be decomposed into at most $leftlfloor frac{n-1}{2}rightrfloor$ cycles. The ErdH{o}s-Gallai conjecture states that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. We show that if $G$ is a sufficiently large graph on $n$ vertices with linear minimum degree, then the following hold. (i) $G$ can be decomposed into at most $frac{n}{2}+o(n)$ paths. (ii) If $G$ is Eulerian, then it can be decomposed into at most $frac{n}{2}+o(n)$ cycles. (iii) $G$ can be decomposed into at most $frac{3 n}{2}+o(n)$ cycles and edges. If in addition $G$ satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such $G$. (iv) $G$ can be decomposed into $max left{frac{odd(G)}{2},frac{Delta(G)}{2}right}+o(n)$ paths, where $odd(G)$ is the number of odd-degree vertices of $G$. (v) If $G$ is Eulerian, then it can be decomposed into $frac{Delta(G)}{2}+o(n)$ cycles. All bounds in (i)-(v) are asymptotically best possible.
Download