![](/files/happy5.png)
Decomposing an eulerian graph into cycles.
Conjecture Every simple eulerian graph on
vertices can be decomposed into at most
cycles.
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \frac{1}{2}(n-1) $](/files/tex/917a680b31340814d24e8e9ea8f3fe6219d868ad.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 a connected graph into paths.
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.