Barnette's Conjecture: is every 3-connected cubic planar bipartite graph Hamiltonian?
Statement
A graph is *cubic* if every vertex has degree $3$, *planar* if it embeds in the plane, *bipartite* if its vertices can be 2-colored so that every edge joins the two colors, and $3$-*connected* if it remains connected after deleting any two vertices. Barnette (1969) conjectured that **every $3$-connected cubic planar bipartite graph has a Hamiltonian cycle** (a cycle visiting every vertex exactly once). Decide the conjecture: prove it, or exhibit a single counterexample. The computational sub-question posed here: verify (or refute) the conjecture for all such graphs up to $n$ vertices, generated exhaustively with a planar-graph generator such as $\texttt{plantri}$.
Acceptance. FULLY RESOLVES: (a) a counterexample -- the adjacency list of a $3$-connected cubic planar bipartite graph together with a certificate that it has no Hamiltonian cycle (an exhaustive/ILP search log) -- or (b) a complete proof. PARTIAL PROGRESS: an exhaustive verification, using $\texttt{plantri}$ to enumerate all $3$-connected cubic planar bipartite graphs, that every such graph on at most $n$ vertices is Hamiltonian for some $n>65$ (report $n$ and the count checked), or a proof for a new structural class. Provide the generator invocation and the Hamiltonicity checker.
Background
Frontier: Holton, Manvel & McKay (1985) verified the conjecture for all such graphs with fewer than $66$ vertices by computer. Recent computer-assisted work extends verification by face size: Schnieders (2025) proves Barnette graphs with all faces of size at most $8$ are Hamiltonian (arXiv:2508.03531, with a case distinction over $339{,}068{,}624$ cases), and every $2$-connected cubic planar graph with faces of size at most $6$ is Hamiltonian (arXiv:2504.20706, 2025). The general conjecture remains open. Source: Open Problem Garden, 'Barnette's Conjecture' (www.openproblemgarden.org/op/barnettes_conjecture), originator D. Barnette; see also MathWorld, 'Barnette's Conjecture'.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Barnette's Conjecture — Open Problem Garden | link |
| REF-02 | Schnieders, Barnette Graphs with Faces up to Size 8 are Hamiltonian (2025) | link |
| REF-03 | Every 2-connected cubic planar graph with faces of size ≤6 is Hamiltonian (2025) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.