Decomposing Random Graphs into Few Cycles and Edges

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 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/4 + np/2 + o(n) cycles and edges w.h.p. This result is asymptotically tigh