Over 50 years ago, Erdýos 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 Sudakov recently proved that this holds for the random graph G(n,p) with probability approaching 1 as n → ∞. In this paper we show that for most edge probabilities G(n,p) can be decomposed into a union of n + np 2 + o(n) cycles and edges whp. This result is asymptotically tight.
['Dániel Korándi', 'Michael Krivelevich', 'Benny Sudakov']
Decomposing random graphs into few cycles and edges