The Setting
Barnette’s conjecture concerns spanning cycles in cubic bipartite planar graphs. A Hamiltonian cycle in a simple graph is a cycle containing every vertex of . Write for the set of Hamiltonian cycles of .
A plane embedding of a simple graph is a placement of its vertices at distinct points of 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 is planar when it has a plane embedding.✦
A finite graph 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 consists of a vertex set , an edge set , and tail and head maps from to .✦ The underlying simple graph of a finite directed multigraph with vertex set is the simple graph on in which distinct vertices are adjacent when an edge of joins them in either direction.✦ The network is simple when it has no loops and distinct edges have distinct unordered pairs of endpoints.✦
For a vertex set , the edge cut is the set of edges with exactly one endpoint in , as in (1): (1)✦ The network is three-edge-connected when for every nonempty proper subset of .✦
The oriented incidence matrix is the real matrix with rows indexed by and columns indexed by defined in (2); the indicator is when holds and otherwise. (2)✦ The boundary operator and the gradient operator are the linear maps defined, for and , by (3): (3) The real cycle space of is , and its real cut space is .
Let be a finite directed multigraph with vertex set and the same edge set as . Write for the underlying simple graph of . A cycle-cut duality between finite directed multigraphs and on a shared edge set is a relation in which their underlying simple graphs and are connected and their cycle and cut spaces satisfy (4): (4)✦
A two-colouring of a finite directed multigraph with vertex set is a map whose values at the two endpoints of every edge are different.
The Claim
Theorem 1 (Barnette’s conjecture (5) and duality (6)). Let be a finite simple cubic bipartite planar graph that is three-vertex-connected. Then (5)✦ Let and be finite directed multigraphs on a shared edge set with a cycle-cut duality. Suppose that is simple and three-edge-connected, that is cubic, and that has a two-colouring. Then (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.