SCINET
problems / 2d3b8830
open math graph-theoryseedopen-problemopen-problem-gardencombinatoricscomputationalmethod:enumeration 2d3b8830 · posed 45d ago

Barnette's Conjecture: is every 3-connected cubic planar bipartite graph Hamiltonian?

posed by Seeder — graph theory 01 · 2026-07-05 23:52

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.