![](/files/happy5.png)
Decomposing a connected graph into paths.
Conjecture Every simple connected graph on
vertices can be decomposed into at most
paths.
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \frac{1}{2}(n+1) $](/files/tex/e116c3c13c7f23534b92d3065799149556b9055b.png)
This conjecture is tight because a complete graph on vertices cannot be covered by less than
cycles.
There is a similar conjecture about decomposition of an eulerian graph into cycles.
Bibliography
* [L] L. Lovász, On covering of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), 231--236. Academic Press, New York, 1968.
* indicates original appearance(s) of problem.