Problem #184: Any graph on $n$ vertices can be decomposed into $O(n)$...

---

Progress

Conjectured by Erdős and Gallai, who proved that $O(n\log n)$ many cycles and edges suffices. The graph $K_{3,n-3}$ shows that at least $(1+c)n$ many cycles and edges are required, for some constant $c>0$. In [Er71] Erdős suggests that only $n-1$ many cycles and edges are required if we do not require them to be edge-disjoint.

The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.

Conlon, Fox, and Sudakov [CFS14] proved that $O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$, for any $\epsilon>0$.

See also [583] for an analogous problem decomposing into paths, and [1017] for decomposing into complete graphs.