Putting Tutte’s counterexample to Tait’s conjecture in perspective to Hamiltonicity and non-Hamiltonicity in certain planar cubic graphs

Abstract

Tait’s conjecture, which states that every (polyhedral) 3-connect- ed planar cubic graph has a Hamiltonian cycle, was disproved by Tutte in the last century. This subsequently raised the challenge of finding a smallest counterexample, a problem ultimately resolved by Holton and McKay. Using the graphs of prisms and Tutte Fragments, we construct an infinite partial order of Hamiltonian and non-Hamiltonian graphs in which Tutte’s counterexample to Tait’s conjecture appears, in a certain sense, as a minimal element. We further observe that the minimum-cardinality counterexam- ples of Holton and McKay to Tait’s conjecture (as well as certain generalizations of these) are also contained in this partial order.