Necessary Structural Conditions for a Minimal Counterexample to Barnette’s Conjecture
Main Article Content
Abstract
Barnette’s conjecture asserts that every cubic, 3-connected, planar, bipartite graph is Hamiltonian. Although the conjecture remains unresolved, computational verification and structural graph theory impose substantial restrictions on any hypothetical counterexample. This article develops a self-contained structural analysis of hypothetical minimal counterexamples. The central object is a hypothetical non-Hamiltonian Barnette graph of minimum order. Elementary counting shows that its order is even and that its two bipartition classes have equal size. Bipartiteness and simplicity exclude facial cycles of odd length and, in particular, triangular faces. Combining the parity restriction with the published computer-assisted verification of Barnette’s conjecture through order 90 yields the lower bound |????(????)| ≥ 92. We also formulate precisely the reduction-and-lifting principle underlying the study of reducible configurations, and identify the additional configuration-specific verification required before that principle can be applied as an unconditional theorem. The results are collected into a structural profile that can guide future enumeration and construction attempts. The article does not claim to settle Barnette’s conjecture.