OctoInformBeta

Barnette’s Hamiltonian-cycle conjecture

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 33-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 33-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.

The Lean library: Hamiltonian

Hamiltonian is a Lean library: 17 items, in seven groups. Each has a page written by OctoInform, listed below.

Section 1. Introduction 2 items
  1. §1 (setting): planarity, connectivity, and a Hamiltonian cycle Plane embeddings and Hamiltonian cycles.
  2. Theorem 1.1 [Barnette's conjecture] Hamiltonian cycles under Barnette’s hypotheses.
Section 2. Plane trees and the triangulation statement 4 items
  1. §2 (setting): plane duality and the triangulation Connected finite plane graphs admit exact duals.
  2. Lemma 2.1 [Complementary tree and forest duality] A dual forest leaves a connected complement.
  3. Theorem 2.2 [Prescribed induced-tree partition] Perfect matchings through any prescribed edge.
  4. §2 (setting): roots, states, and paired states Corner choices define states and pairs.
Section 3. Two disjoint states 1 item
  1. Proposition 3.1 [Existence of a pair] Two disjoint states from cut conditions.
Section 4. The disk identity 2 items
  1. §4 (setting): the signed edge weight Cyclic signs and the black boundary sum.
  2. Lemma 4.1 [Disk identity] State cycles bound signed shores.
Section 5. A weighted cancellation argument 4 items
  1. §5 (setting): the opposite graph and the weighted sum Opposite edges and weighted pair terms.
  2. Proposition 5.1 [Existence of a forest pair] Existing pairs admit a forest second state.
  3. Lemma 5.2 [Cancellation at a fixed second state] Partner phases cancel under the disk condition.
  4. Lemma 5.3 [Positive spoke circulations; restricted replacement] White charges prescribe the signs of cycle slopes.
Section 6. Recovering the two induced trees 2 items
  1. Lemma 6.1 [One root per component; construction consequence] Two root edges preserve acyclicity.
  2. Lemma 6.2 [The selected set is a forest] Forest criteria for selected dual sides.
Section 7. Separating triangles and the Hamiltonian cycle 2 items
  1. §7 (proof setting): gluing the prescribed selection Compatible capped matchings glue together.
  2. Corollary 7.1 [Avoiding any prescribed edge] Perfect matchings with a prescribed edge.

No item matches.