Barnette's conjecture

It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

Therefore, Barnette's conjecture may be stated in an equivalent form: suppose that a three-dimensional simple convex polyhedron has an even number of edges on each of its faces.

Kelmans (1994)[2] showed that Barnette's conjecture is equivalent to a superficially stronger statement, that for every two edges e and f on the same face of a bipartite cubic polyhedron, there exists a Hamiltonian cycle that contains e but does not contain f. Clearly, if this statement is true, then every bipartite cubic polyhedron contains a Hamiltonian cycle: just choose e and f arbitrarily.

Barnette's conjecture is also 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.

[3] Although the truth of Barnette's conjecture remains unknown, computational experiments have shown that there is no counterexample with fewer than 86 vertices.

A related conjecture of Barnette states that every cubic polyhedral graph in which all faces have six or fewer edges is Hamiltonian.

The left and right are the same graph, displayed in different ways. The graph is planar , because it can be arranged so that no edges overlap, and is bipartite , because the vertices can be colored so that there is no edge connecting 2 vertices of the same color (red and blue here). It is also cubic , because every vertex has 3 edges connected to it (every vertex has degree 3), and polyhedral , because the graph stays connected when removing any 2 points (also known as 3-vertex-connected ). The conjecture states that every graph which meets all these criteria is also Hamiltonian , meaning there is a cycle that goes through all vertices of the graph (one such is drawn green here).