# A conjecture of Erdös and Gallai [4], 1959.

Every connected graph on $$n$$ vertices can be edge-partitioned into at most $$\lfloor (n+1)/2 \rfloor$$ paths.

Erdös and Gallai[4] showed that a connected graph with minimum degree $$d$$ and at least $$2d+1$$ vertices has a path of length at least $$2d+1$$. Lovász [6] showed that every graph on $$n$$ vertices can be edge-partitioned into at most $$\lfloor n/2 \rfloor$$ cycles and paths.

A closely related problem is the following conjecture of Hajos[6]:

Conjecture 1   Every graph $$G$$ on $$n$$ vertices with all degrees even can be decomposed into at most $$\lfloor n/2 \rfloor$$ edge-disjoint cycles.

Chung [3] proved that a connected graph on $$n$$ vertices can be partitioned into at most $$\lceil n/2 \rceil$$ edge-disjoint trees. Pyber [8] showed that every connected graph on $$n$$ vertices can be covered by at most $$n/2 +O(n^{3/4})$$ paths.

A linear forest is a disjoint union of paths. The following related conjecture is due to Akiyama, Exoo, Harary[1] and Hilton[5].

Conjecture 2   A graph of maximum degree $$\Delta$$ can be covered by $$\lceil \frac{\Delta+1}{2} \rceil$$ linear forests.

It is easy to see that $$\lceil \frac{\Delta+1}{2} \rceil$$ linear forests are necessary to cover a regular graph of degree $$\Delta$$. Alon[2] proved that a graph of maximum degree $$\Delta$$ can be covered by $$\Delta/2 + c \Delta^{2/3} ( \log \Delta)^{1/3}$$ linear forests. In 1995, McDiarmid and Reed [7] proved that almost every graph with maximum degree $$\Delta$$ can be covered by $$\lceil \Delta /2 \rceil$$ linear forests.

Bibliography
1 J. Akiyama, G. Exoo and F. Harary. Covering and packing in graphs III, Cyclic acyclic invariants, Math. Slovaca 30 (1980), 405-417.

2 N. Alon, The linear arboricity of graphs. Israel J. Math. 62 (1988), 311-325.

3 F. R. K. Chung. On partitions of graphs into trees, Discrete Math. 23 (1978), 23-30.

4 P. Erdös and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337-356.

5 A. J. W. Hilton. Canonical edge-colourings of locally finite graphs. Combinatorics 2 (1982), 37-51.

6 L. Lovász, On covering of graphs, Theory of Graphs, Proc. Coll. Tihany, 1966 (P. Erdös and G. O. H. Katona, eds.), 231-236, Academic Press, New York, 1968.

7 C. McDiarmid, B. Reed. Almost every graph can be covered by $$\lceil (\Delta +1)/2 \rceil$$ linear forests, Comb. Prob. Compl 4 (1995), 257-268.

8 L. Pyber, Covering the edges of a connected graph by paths, J. Comb. Theory Ser. B 66 (1996), 152-159.