On prisms, Mِbius ladders and the cycle space of dense graphs

For a graph G , let | G | denote its number of vertices, δ ( G ) its minimum degree and Z 1 ( G ; F 2 ) its cycle space. Call a graph Hamilton-generated if and only if every cycle in G is a symmetric difference of some Hamilton circuits of G . The main purpose of this paper is to prove: for every γ > 0 there exists n 0 ∈ Z such that for every graph G with | G | ⩾ n 0 vertices, (1) G ) ⩾ ( 1 2 + γ ) | G | and | G | is odd, then G is Hamilton-generated, G ) ⩾ ( 1 2 + γ ) | G | and | G | is even, then the set of all Hamilton circuits of G generates a codimension-one subspace of Z 1 ( G ; F 2 ) and the set of all circuits of G having length either | G | − 1 or | G | generates all of Z 1 ( G ; F 2 ) , G ) ⩾ ( 1 4 + γ ) | G | and G is balanced bipartite, then G is Hamilton-generated. ese degree-conditions are essentially best-possible. The implications in (1) and (2) give an asymptotic affirmative answer to a special case of an open conjecture which according to [I.B.-A. Hartman, Long cycles generate the cycle space of a graph, European J. Combin. 4 (3) (1983) 237–246] originates with A. Bondy.