Barnette's conjecture is an unsolved problem in graph theory concerning Hamiltonian cycles. It was proposed by David W. Barnette in 1969 (as "Conjecture 5" in Recent Progress in Combinatorics) and states:
Every 3-connected cubic bipartite planar graph is Hamiltonian.
Equivalently: every bipartite polyhedral graph in which every vertex has degree three contains a Hamiltonian cycle (a cycle passing through every vertex exactly once).
Definitions and equivalent formulations
- Planar: can be drawn in the plane without edge crossings.
- Polyhedral: planar and 3-vertex-connected (the graph of a convex polyhedron, by Steinitz's theorem).
- Cubic (3-regular): every vertex has exactly three incident edges.
- Bipartite: the vertices can be divided into two classes such that every edge joins vertices of different classes.
- Hamiltonian: contains a cycle visiting every vertex exactly once.
By Steinitz's theorem, the conjecture can be restated in geometric terms: if a three-dimensional simple convex polyhedron has an even number of edges on each of its faces, then the graph of the polyhedron has a Hamiltonian cycle. This follows because a planar graph is bipartite exactly when every face cycle has even length, and it is cubic exactly when the polyhedron is simple.
Further equivalent formulations are known:
- Kelmans (1994) showed the conjecture is equivalent to a superficially stronger statement: for any two edges e and f lying on the same face of a cubic bipartite polyhedral graph, there is a Hamiltonian cycle containing e and avoiding f.
- The conjecture is equivalent to the statement that the vertices of the dual of every cubic bipartite polyhedral graph can be partitioned into two subsets whose induced subgraphs are trees (Florek 2010).
- It has also been reformulated in matching-theoretic terms, reducing it to the statement that all cubic 3-connected planar bipartite braces are Hamiltonian (Gorsky, Steiner and Wiederrecht, 2022, preprint).
Historical background
The conjecture sits between two earlier, discredited conjectures:
- Tait's conjecture (P. G. Tait, 1884): every cubic 3-connected planar graph is Hamiltonian. This was disproved by W. T. Tutte (1946), who constructed a 46-vertex counterexample; the smallest counterexample, the Barnette–Bosák–Lederberg graph, has 38 vertices and was shown minimal by Holton and McKay (1988).
- Tutte's conjecture (1971): every cubic 3-connected bipartite graph is Hamiltonian. This was disproved by the Horton graph (J. D. Horton, 1976/1982); the smallest known counterexample has 50 vertices (Georges, 1989).
Barnette's conjecture is the combination of the two earlier statements restricted to the planar bipartite case: it asserts that every counterexample to Tait's conjecture is non-bipartite, and that Tutte's counterexamples necessarily fail planarity. Restating this way, it is also phrased as: every counterexample to Tait's conjecture must be non-bipartite.
Partial results
- Goodey (1975) proved the conjecture for graphs in which every face has four or six sides.
- Holton, Manvel and McKay (1985) verified the conjecture computationally for all graphs with fewer than 66 vertices; this bound was later extended. A 2002 communication by Aldred, Brinkmann and McKay announced verification up to 84 vertices inclusive.
- If the conjecture is false, then testing whether a bipartite cubic polyhedron is Hamiltonian is NP-complete (Feder and Subi, 2006). Without 3-connectedness, deciding Hamiltonicity for 2-connected cubic planar bipartite graphs is already NP-complete (Akiyama, Nishizeki and Saito, 1980). Together these results place the problem on the boundary between polynomial-time solvability and NP-completeness.
- Alt, Payne, Schmidt and Wood (2016) gave results based on coloring the dual graph.
- Bagheri Gh., Feder, Fleischner and Subi (2021) proved Hamiltonicity for the leapfrog extension of any cyclically 4-edge-connected bipartite cubic planar graph, extending Goodey's result.
- More recent preprints report further partial progress, including sufficient conditions on large faces (Florek) and Hamiltonicity for all such graphs whose faces have size at most 8 (Schnieders, 2025). These are not yet part of the established literature.
Related conjecture
A separate conjecture of Barnette states that every cubic 3-connected planar graph in which all faces are hexagons is Hamiltonian. Aldred et al. (2000) verified it for graphs with fewer than 177 vertices, and Kardoš (2020) gave a computer-assisted proof. A related case is that of planar cubic graphs in which every face has at most six edges, proven for fullerene graphs and related classes by Kardoš (2020). The intersection of this conjecture with Barnette's conjecture — cubic bipartite polyhedral graphs in which all faces have four or six edges — was proved by Goodey (1975).
Status
The conjecture remains open. It is listed among well-known open problems in graph theory, and the standard reference is Holton, Manvel and McKay (1985), with surveys including that of Hertel (2005).
