Contractible edges in longest cycles in non-Hamiltonian graphs (Q1336689)

This paper addresses the question of how contractible edges are distributed in longest cycles in 3-connected graphs. It establishes the fact that in non-Hamiltonian 3-connected graphs, each longest cycle includes at least 6 contractible edges. An edge in a 3-connected graph is called contractible if the graph obtained from the contraction of the edge is also 3-connected.