**Conjecture**Every simple connected graph on vertices can be decomposed into at most paths.

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.