Erdős Problem #184

declared status 'open'. Formalized: yes. Any graph on $n$ vertices can be decomposed into $O(n)$ many edge-disjoint cycles and edges. Current best: The best bound available is due to Buci\'{c} and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function. Prize: no. Tags: cycles, graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.