A graph is cubic if every vertex has degree three. A graph is bipartite if its vertices admit a partition into two classes with no edge inside either class. A graph is -vertex-connected if it has at least four vertices and remains connected after deleting any set of at most two vertices. A Hamiltonian cycle is a cycle that visits every vertex exactly once. Barnette’s conjecture asks whether every finite simple cubic bipartite planar -vertex-connected graph has a Hamiltonian cycle.
Goodey proved Barnette’s conjecture when every face has size four or six. Schnieders proved it when every face has size at most eight. Alt, Payne, Schmidt, and Wood established that Hamiltonicity in this class corresponds to a partition of the dual triangulation’s vertices into two sets, each inducing a tree.
The preprint proves Barnette’s conjecture. The preprint proves that every simple sphere triangulation with at least four vertices and faces properly colored black and white admits, for any prescribed face and an edge of that face, a vertex partition into two sets inducing trees, with the endpoints of the prescribed edge in one set and the third vertex of the prescribed face in the other.
The Lean library Hamiltonian proves the Hamiltonian-cycle conclusion. An edge weighting on an oriented graph has zero divergence when the total incoming weight equals the total outgoing weight at every vertex. A vertex potential assigns a number to each vertex. Its difference across an oriented edge is the potential at the terminal vertex minus the potential at the initial vertex. The Lean library assumes that an edge weighting has zero divergence on the original graph exactly when its weights on the dual edges are differences of vertex potentials on a finite oriented dual graph. Under this hypothesis, the Lean library’s counterpart of the induced-tree partition states that every prescribed edge of a finite simple cubic bipartite graph with no edge cut of fewer than three edges belongs to a perfect matching with connected spanning complement. Lean has checked every result of the Lean library. The Lean library is therefore the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its Lean declaration, with the preprint’s statement beside it when the two differ. The preprint is a guide to the order and names of the results.
Hamiltonian is a Lean library: 17 items, in seven groups. Each has a page written by OctoInform, listed below.
No item matches.