The cycle space of a graph G, denoted C (G), is a vector space over F₂, spanned by all incidence vectors of edge-sets of cycles of G. If G has n vertices, then Cₙ (G) denotes the subspace of C (G), spanned by the incidence vectors of Hamilton cycles of G. A classical result in the theory of random graphs asserts that for G G (n, p), asymptotically almost surely the necessary condition δ (G) 2 is also sufficient to ensure Hamiltonicity. Resolving a problem of Christoph, Nenadov, and Petrova, we augment this result by proving that for G G (n, p), with n being odd, asymptotically almost surely the condition δ (G) 3 (observed to be necessary by Heinig) is also sufficient for ensuring Cₙ (G) = C (G). That is, not only does G typically have a Hamilton cycle, but its Hamilton cycles are typically rich enough to span its cycle space.
Hefetz et al. (Tue,) studied this question.