Barnette's Conjecture

Barnette's conjecture asserts that every 3-connected bipartite cubic planar graph is Hamiltonian. The only graph on nine or fewer vertices satisfying Barnette's conditions is the cubical graph, which is indeed Hamiltonian. The skeletons of the truncated octahedron, great rhombicuboctahedron, and great rhombicosidodecahedron also satisfy the conditions and, since they are Archimedean solids, are indeed Hamiltonian. Holton et al. (1985) proved that all graphs having fewer than 66 vertices satisfy the conjecture, while the general conjecture has been the subject of a subsequent proof announcement.

The separate face-size formulation asserts that all cubic, 3-connected, planar graphs with every face of size at most 6 are Hamiltonian. Aldred et al. (2000) verified this assertion for all graphs with fewer than 177 vertices. Kardoš (2020) subsequently proved the general face-size assertion using a computer-assisted argument.