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

2025/10/09 by Herbert Fleischner, Fleischner, Herbert, Enrico Iurlano +3
Computer Science · Materials Science · Mathematics · #05C38 #05C45 #05C83 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Quasicrystal Structures and Properties

paper · pdf · doi:10.48550/arxiv.2510.08310

openalex publication_date 2025/10/09 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28

Abstract

Using the graphs of prisms and Tutte Fragments, we construct an infinite family 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 observe that generalizations of the minimum-cardinality counterexamples of Holton and McKay to Tait's conjecture are as well contained in this family.

Citations

• Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette's Conjecture

Related

• On minors of non-hamiltonian graphs
• Algorithmic proof of Barnette's Conjecture
• Equivalent formulation of Thomassen's conjecture using Tutte paths in claw-free graphs
• Hamiltonicity of planar graphs with a forbidden minor
• Criticality of counterexamples to toroidal edge-hamiltonicity