∑math20

Combinatorics · Result 180

Barnette’s Hamiltonian-cycle conjecture

1 paperLean

Proves that every finite simple cubic bipartite planar 3-vertex-connected graph has a Hamiltonian cycle, resolving Barnette's conjecture. Equivalently, every three-edge path in a finite simple cubic 3-vertex-connected bipartite Pfaffian graph lies in a Hamiltonian cycle.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 1

First page of Paired states and Hamiltonian cycles in cubic bipartite planar graphs

Paired states and Hamiltonian cycles in cubic bipartite planar graphs

OpenAI · September 24, 2026

We prove Barnette's conjecture: every finite simple cubic bipartite planar 3-vertex-connected graph has a Hamiltonian cycle.

Read PDF Download Source

Cite
@misc{OAI:Paired-states-and-Hamiltonian-cycles-in-cubic-bipartite-planar-graphs-September-24-2026,
  author = {{OpenAI}},
  title = {{Paired states and Hamiltonian cycles in cubic bipartite planar graphs}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Paired-states-and-Hamiltonian-cycles-in-cubic-bipartite-planar-graphs-September-24-2026/paper.pdf}{OAI:Paired-states-and-Hamiltonian-cycles-in-cubic-bipartite-planar-graphs-September-24-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

Barnette's conjecture states that every finite simple cubic bipartite planar graph that is 3-vertex-connected has a Hamiltonian cycle. The formalization proves this statement for every such graph. The selected result is the existence of a cycle visiting every vertex exactly once.

Comparator links

ResultComparator statement
Barnette's Hamiltonian-cycle conjectureBarnetteHamiltonian.lean

Scope note on GitHub →