Barnette’s Hamiltonian conjecture

Can every network in Barnette’s class be toured along its existing connections, visiting each dot once before returning to the start? A cube’s corners and edges give an example: go around three edges of one square face, cross to the opposite face, follow three edges there, and cross back. The class requires three connections at each dot, a drawing without crossings, two groups with every connection running between groups, and continued connectedness after deleting any one or two dots. The cube has all four properties. It is unknown whether every network satisfying them has such a tour.[1] [2]

Can every finite graph satisfying Barnette’s four restrictions contain a closed route using only its own edges and visiting every vertex exactly once? This is a Hamiltonian cycle. The restrictions are 3-regularity, planarity, bipartiteness and 3-connectedness: three incident edges per vertex, a crossing-free drawing, a split with all edges between the two parts, and connectedness after deletion of any set of at most two vertices. For the cube, label corners by three-bit strings and join pairs differing in one bit. A route starts $000\to001\to011\to010\to110$, then continues $110\to111\to101\to100\to000$. The shared corner 110 joins the two parts. Each step changes one bit, and the complete route visits all eight corners before returning to its start. Bit-sum parity gives the bipartition. This eligible example illustrates the target, not a tour construction for every graph in the class.[1] [2]

The full class remains unresolved. Approximate results allow some steps that are not edges of the original graph. A preprint claims the exact tour when every face has at most eight edges; unrestricted face sizes remain outside that result.[1] [2]

The published approximation gives a vertex order that can be completed to a cycle by adding edges, with at least five-sixths of consecutive pairs already joined. The required Hamiltonian cycle must use only original edges. Schnieders’s preprint claims Hamiltonicity for the bounded-face case, with every face of size at most eight. The preprint uses computational case analysis, and the restriction does not cover arbitrary face sizes.[1] [2]

At each dot a tour uses two of the three connections, leaving one unused. Those unused connections pair up all the dots. Conversely, choosing one such pairing can leave several separate loops instead of a single tour. This connects local pairing choices with global connectedness: the problem asks how the graph’s structure lets those loops become one.[1] [2]

There is a useful local-to-global reformulation. In a 3-regular graph, removing a Hamiltonian cycle leaves one edge incident at each vertex: a perfect matching. Conversely, removing any perfect matching leaves degree two at every vertex, so the remaining edges are a disjoint union of cycles. The extra requirement is that this union be connected. Barnette’s problem thus links vertex pairings with the topology of spanning cycles; its structural assumptions must do more than permit local choices, because those choices can create several loops.[1] [2]