OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Theorem 1.1 [Barnette's conjecture]: Finite simple cubic bipartite planar graphs with three-vertex connectivity, and a cycle-cut formulation for networks

Hamiltonian cycles under Barnette’s hypotheses.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Barnette’s conjecture concerns spanning cycles in cubic bipartite planar graphs. A Hamiltonian cycle in a simple graph GG is a cycle containing every vertex of GG. Write ℋ(G)\mathcal H(G) for the set of Hamiltonian cycles of GG.

A plane embedding of a simple graph GG is a placement of its vertices at distinct points of ℝ2\mathbb R^2 together with a representation of each edge by an injective continuous arc between its endpoints, with reversal of an edge reversing its arc. Each arc meets a vertex only at the corresponding endpoint, and arcs of distinct edges have disjoint interiors. A simple graph GG is planar when it has a plane embedding.✦

A finite graph GG is three-vertex-connected when it has at least four vertices and remains connected after deletion of any set of at most two vertices.✦

Networks and Duality

A finite directed multigraph NN consists of a vertex set VV, an edge set EE, and tail and head maps from EE to VV.✦ The underlying simple graph GNG_N of a finite directed multigraph NN with vertex set VV is the simple graph on VV in which distinct vertices are adjacent when an edge of NN joins them in either direction.✦ The network NN is simple when it has no loops and distinct edges have distinct unordered pairs of endpoints.✦

For a vertex set U⊆VU\subseteq V, the edge cut δN(U)\delta_N(U) is the set of edges with exactly one endpoint in UU, as in (1): δN(U)={e∈E:|{tail⁡N(e),head⁡N(e)}∩U|=1,tail⁡N(e)≠head⁡N(e)}.\delta_N(U)= \{e\in E: |\{\operatorname{tail}_N(e),\operatorname{head}_N(e)\}\cap U|=1, \ \operatorname{tail}_N(e)\ne\operatorname{head}_N(e)\}.(1)✦ The network NN is three-edge-connected when |δN(U)|≥3|\delta_N(U)|\geq 3 for every nonempty proper subset UU of VV.✦

The oriented incidence matrix BNB_N is the real matrix with rows indexed by VV and columns indexed by EE defined in (2); the indicator 𝟏P\mathbf 1_P is 11 when PP holds and 00 otherwise. (BN)ve=𝟏head⁡N(e)=v−𝟏tail⁡N(e)=v.(B_N)_{ve}= \mathbf 1_{\operatorname{head}_N(e)=v} -\mathbf 1_{\operatorname{tail}_N(e)=v}.(2)✦ The boundary operator ∂N:ℝE→ℝV\partial_N:\mathbb R^E\to\mathbb R^V and the gradient operator ∇N:ℝV→ℝE\nabla_N:\mathbb R^V\to\mathbb R^E are the linear maps defined, for x∈ℝEx\in\mathbb R^E and f∈ℝVf\in\mathbb R^V, by (3): (∂Nx)(v)=∑e∈E(BN)vex(e),(∇Nf)(e)=f(head⁡N(e))−f(tail⁡N(e)).(\partial_N x)(v)=\sum_{e\in E}(B_N)_{ve}x(e), \qquad (\nabla_N f)(e)=f(\operatorname{head}_N(e))-f(\operatorname{tail}_N(e)).(3) The real cycle space of NN is ker⁡∂N\ker\partial_N, and its real cut space is im⁡∇N\operatorname{im}\nabla_N.

Let DD be a finite directed multigraph with vertex set WW and the same edge set EE as NN. Write GDG_D for the underlying simple graph of DD. A cycle-cut duality between finite directed multigraphs NN and DD on a shared edge set is a relation in which their underlying simple graphs GNG_N and GDG_D are connected and their cycle and cut spaces satisfy (4): ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\ker\partial_N=\operatorname{im}\nabla_D, \qquad \ker\partial_D=\operatorname{im}\nabla_N.(4)✦

A two-colouring χ\chi of a finite directed multigraph NN with vertex set VV is a map χ:V→{0,1}\chi:V\to\{0,1\} whose values at the two endpoints of every edge are different.

The Claim

Theorem 1 (Barnette’s conjecture (5) and duality (6)). Let GG be a finite simple cubic bipartite planar graph that is three-vertex-connected. Then ℋ(G)≠⌀.\mathcal H(G)\ne\varnothing.(5)✦ Let NN and DD be finite directed multigraphs on a shared edge set with a cycle-cut duality. Suppose that NN is simple and three-edge-connected, that GNG_N is cubic, and that NN has a two-colouring. Then ℋ(GN)≠⌀.\mathcal H(G_N)\ne\varnothing.(6)✦

What Is Checked

The graph statement is over finite simple graphs with plane embeddings and three-vertex connectivity, and the network statement is over finite vertex and edge sets with real boundary and gradient operators on a shared edge set.