1. The question
Can one trace a closed route along the edges of a polyhedral graph, visiting every vertex exactly once? Such a route is a Hamiltonian cycle. Even a highly connected planar graph need not have one, so additional structure matters.
Barnette’s conjecture identifies a particularly elegant set of conditions: every vertex has degree three, the graph is bipartite, and it is planar and 3-vertex-connected. The manuscript claims that every finite simple graph satisfying these conditions has a Hamiltonian cycle, with no restriction on face sizes.
The proof changes viewpoint. Instead of trying to join many partial cycles directly, it studies the planar dual and seeks a partition of its vertices into two induced trees. A weighted sum over pairs of matching states is used to force the required acyclic structure.
2. Background and essential definitions
A graph is cubic when every vertex has degree three. It is bipartite when its vertices can be split into two classes so that every edge joins different classes. Equivalently, it has no odd cycle.
A planar graph can be drawn on a sphere without edge crossings. It is 3-vertex-connected if it has at least four vertices and deleting any one or two vertices leaves it connected. A planar 3-connected graph is often called polyhedral.
A Hamiltonian cycle visits every vertex exactly once before returning to its starting point. It uses two incident edges at each vertex. In a cubic graph, its unused edges form a perfect matching, meaning that each vertex belongs to exactly one unused edge.
However, the reverse local condition is insufficient. Removing a perfect matching leaves degree two at every vertex, but the result may be several disjoint cycles. The problem is obtaining one connected spanning cycle.
Given a sphere drawing, the dual graph has one vertex for each face and one dual edge crossing each original edge. Because the original graph is cubic, every face of the dual is a triangle. Because the original graph is bipartite, these dual triangles can be colored black and white with opposite colors across every edge.
An induced tree on a vertex set contains every edge of the ambient graph between those vertices and has no cycle. Requiring induced trees is stronger than merely finding two connected spanning subgraphs on the two parts.
3. Development history and previous partial results
The problem belongs to a long line of Hamiltonicity questions for polyhedral graphs. Tait conjectured that every cubic polyhedral graph was Hamiltonian. Tutte’s 1946 counterexample disproved that broader statement. Barnette’s conjecture adds bipartiteness and was recorded by Grünbaum in the 1969 Waterloo proceedings.
Much progress used restrictions on face sizes. Goodey proved the case where every face is a quadrilateral or hexagon. These are natural lengths in a bipartite planar graph because every facial cycle has even length.
Feder and Subi allowed arbitrarily large faces in one class of a proper three-coloring of the faces, while requiring quadrilaterals or hexagons in the other two classes. Their argument used trees of faces after contracting a distinguished class.
Kardoš proved the related Barnette–Goodey conjecture for cubic polyhedral graphs with face sizes at most six without assuming bipartiteness. That is a different balance of hypotheses: stronger face restrictions allow the bipartite requirement to be removed.
More recently, Schnieders proved Barnette’s conjecture when all faces have size at most eight. The new manuscript claims the full bipartite class, including graphs with arbitrarily large faces.
The dual formulation also has a history. Stein related Hamiltonian cycles to region partitions, and Alt, Payne, Schmidt and Wood formulated the equivalence using two induced trees in a triangulation. Matching-theoretic equivalences developed by Gorsky, Steiner and Wiederrecht supply further consequences once the general conjecture is established.
4. What the new manuscripts claim
The main statement is:
M1 claims Hamiltonicity for every finite simple cubic bipartite planar graph satisfying 3-vertex-connectivity.
The manuscript proves a more locally prescribed dual statement. Let be a sphere triangulation with black and white faces alternating across every edge. Choose any facial triangle and one of its edges. The vertices of can be partitioned into two sets, each inducing a tree, with the chosen edge’s endpoints in one set and the triangle’s third vertex in the other.
This prescribed pattern gives a useful consequence in the original graph: for every specified edge , there is a Hamiltonian cycle avoiding . The paper credits this as a previously known equivalent global strengthening of Barnette’s conjecture, rather than treating the equivalence itself as new.
Through another published equivalence, it also concludes that every three-edge path in a finite simple cubic, bipartite, 3-connected Pfaffian graph extends to a Hamiltonian cycle. A graph is Pfaffian if it has an orientation in which each even cycle whose deletion leaves a perfect matching has an odd number of edges directed along either traversal of that cycle. This is a matching-theoretic condition that includes planar graphs and also allows some nonplanar ones.
The principal theorem is an existence claim. Although its ingredients include finite matchings and flows, the manuscript does not assert a polynomial-time algorithm for finding the Hamiltonian cycle. The finite weighted sum used to establish existence may involve many states.
5. Why the advance matters
Importance: 4/5. Barnette’s conjecture is a major longstanding problem about when local degree, planarity, connectivity and parity force a global spanning route. The claim removes the face-size restrictions of earlier partial results.
The central difficulty is connectedness of the route. It is comparatively easy to describe a spanning structure that gives every vertex degree two; preventing it from breaking into multiple cycles is much harder. The dual-tree construction builds that global connectedness into the argument.
The prescribed local pattern is also significant. Recursive arguments cut a graph into pieces, but independently chosen solutions may fail to match along their boundaries. Retaining a small boundary condition allows the manuscript to glue the pieces back together while preserving induced trees. The importance rating reflects both the full conjecture and this structural treatment of compatibility.
6. The main idea
Translate one cycle into two trees
Suppose the dual triangulation’s vertices have been split into two induced trees. Every triangular face then has exactly one edge inside a tree class: it cannot have all three vertices in one class, because that would create a cycle.
Discard those tree edges and return to the original graph by duality. Exactly two selected edges meet each original vertex, so the result has degree two everywhere. Complementary planar tree–forest duality supplies connectedness. A finite connected graph of degree two is one cycle, hence a Hamiltonian cycle.
The task is therefore to construct the two-tree partition, including the prescribed pattern on a chosen triangle.
Pair matching states
First assume there is no separating triangle, meaning no triangular cycle with vertices strictly on both sides. Choose one black triangle as the outer face and call its vertices roots.
The remaining black triangles and the nonroot vertices have equal cardinality. A state matches every remaining black triangle to one incident nonroot vertex, using each such vertex once. A pair of states chooses different vertices in every triangle. A planar counting inequality and an integral flow argument establish that such pairs exist.
For the second state , select the edge opposite its chosen vertex in each black triangle. Call the selected edge set . The desired intermediate object is a state for which is a forest.
Cancel the cyclic states, then show something survives
The manuscript introduces a finite weighted sum over pairs of states. The same sum is analyzed in two ways.
When the second state is fixed and contains a cycle, a reversal changes the first state and pairs two terms with opposite phases but equal real weights. These contributions cancel. Thus only pairs with acyclic can survive in the total.
To prove that the sum is not zero, the terms are regrouped according to the undirected edges joining the two chosen vertices in each triangle. Their components are cycles, and choosing a pair of states amounts to choosing orientations of those cycles.
Suitable positive circulations determine the real weights. A planar disk identity controls the phases. Near a chosen parameter value, the groups with the fewest cycles have leading contributions with a common phase and positive magnitude, so they cannot cancel each other. Some forest state must therefore exist.
From that forest, complementary plane-tree duality produces the edge structure needed for the two induced trees. This is an existence mechanism based on cancellation and nonvanishing, not a claim that arbitrary local choices already produce the correct forest.
Glue across separating triangles
If a separating triangle is present, split the triangulation into two smaller ones and cap each side along the triangle. Apply the theorem recursively while prescribing matching labels on the shared boundary.
For each tree class, the two smaller induced trees meet in either one vertex or one edge. Gluing trees along such a connected intersection produces a tree. The preserved facial pattern is what makes this final assembly possible.
7. Scope, limitations, and open questions
All four graph hypotheses remain part of the main theorem. Tutte’s earlier example already shows that removing bipartiteness from the cubic polyhedral setting does not preserve the conclusion. The manuscript does not claim Hamiltonicity for arbitrary bipartite planar graphs or for graphs with weaker connectivity.
The output is a Hamiltonian cycle, not a uniquely determined one or a lower bound on how many such cycles exist. Avoiding one specified edge is guaranteed, but arbitrary collections of forbidden edges are not covered by that statement.
The Pfaffian extension uses a specific published equivalence and retains cubicity, bipartiteness and 3-connectivity. It is not a blanket nonplanar generalization.
Finally, efficient construction remains separate from the stated existence argument. A matching or flow step can be algorithmic while a later nonvanishing argument is still nonconstructive in its complexity guarantees. Determining useful algorithms, optimized structural criteria or stronger prescribed-route properties requires further results.
8. Sources and further reading
The manuscript’s first two pages explain the dual formulation, the paired states and the two distinct regroupings of the weighted sum. Its final section records edge avoidance and the Pfaffian consequence.
Primary background includes Tutte’s non-Hamiltonian cubic polyhedron, Goodey’s quadrilateral–hexagon case, Schnieders’s face-size-eight result, Alt–Payne–Schmidt–Wood’s dual viewpoint, and Gorsky–Steiner–Wiederrecht’s matching equivalences. These distinguish the earlier reductions from the general existence claim explained here.
Source manuscripts
- M1. OpenAI, Paired states and Hamiltonian cycles in cubic bipartite planar graphs (September 24, 2026).
Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.