Barnette's Conjecture

Barnette's conjecture, posed by David Barnette in 1969 [Barnette1969], asserts that every finite simple planar graph that is cubic, bipartite and $3$-vertex-connected contains a Hamiltonian cycle. It refines a classical theme: Tait's nineteenth-century conjecture that all cubic $3$-connected planar graphs are Hamiltonian was disproved by Tutte, and bipartiteness is the extra hypothesis under which Hamiltonicity is expected to be restored.

Substantial partial progress exists. Hamiltonian cycles are known to be forced under a variety of additional restrictions, most notably conditions bounding the sizes of faces or imposing extra structure on the plane embedding. Recent work has brought matching theory to bear on the problem [GorskySteinerWiederrecht2022Barnette] and has produced further sufficient conditions for Hamiltonicity within this class [Florek2025Barnette].

Despite this accumulation of special cases, the unrestricted class is unresolved: no argument covers all cubic $3$-connected plane bipartite graphs, and no counterexample is known. The conjecture remains open.