Towards the Erdős-Gallai Cycle Decomposition Conjecture

Matija Bucić, Richard Montgomery

In the 1960's, Erdős and Gallai conjectured that the edges of any $n$-vertex graph can be decomposed into $O(n)$ cycles and edges. We improve upon the previous best bound of $O(n\l…