Decomposing random graphs into few cycles and edges

Dániel Korándi, Michael Krivelevich, Benny Sudakov

Over 50 years ago, Erdős and Gallai conjectured that the edges of every graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. Among other results, Conlon, Fox and S…