Erdős Problems

OPEN

Any graph on $n$ vertices can be decomposed into $O(n)$ many cycles and edges.

Conjectured by Erdős and Gallai, who proved that $O(n\log n)$ many cycles and edges suffices.

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$.