The Setting
A network on finite vertex and edge sets and is a directed multigraph assigning each edge a tail and a head in .✦ The underlying simple graph of a network has vertex set ; two distinct vertices are adjacent when they are the endpoints of an edge of .✦ A network is simple when it has no loops and at most one edge with any given unordered pair of endpoints.✦ A network is cubic when every vertex of its underlying simple graph has degree three.
An edge of is incident to a vertex when is its tail or its head.✦ The vertex star of a vertex in a network is the set of all edges of incident to .✦ A perfect matching of is a subset of satisfying (1). (1)
For a map , the edge restriction is the network on vertex set and edge set with endpoints and for .✦ For a subset , write for restriction along the inclusion of into .
For a vertex set , the edge cut is the set of edges with exactly one endpoint in .✦ A network is three-edge-connected when every nonempty proper vertex set satisfies (2). (2)✦
A black color class gives a bipartition of when every edge has exactly one endpoint in .
The oriented incidence matrix , boundary operator , and gradient operator of are the real matrix and maps defined in (3); here is an edge weight and is a vertex potential. (3) The real cycle space of a network is the kernel of the boundary operator of ; the real cut space of is the range of the gradient operator of . Cycle cut duality is the relation between a network and a network on a vertex set and the same edge set that holds when their underlying simple graphs and are connected and satisfy (4). (4)✦
A Hamiltonian cycle in a simple graph is a closed walk in based at a vertex that visits every vertex of exactly once before returning to .
The Claim
Theorem 1. Let be a finite simple cubic network. For every perfect matching , the complementary graph satisfies (5). (5)✦ Assume in addition that is three-edge-connected, that gives a bipartition of , and that has a cycle cut duality with . For every prescribed edge , the assertion (6) holds. (6)✦ Under these additional hypotheses, (7) holds as well. (7)✦
In the paper, the result reads: every finite simple cubic bipartite planar -vertex-connected graph has, for each edge , a Hamiltonian cycle avoiding .
What Is Checked
The matching statement (5) is stated over finite simple cubic networks; (6) and (7) additionally require three-edge connectivity, a bipartition, and a cycle cut duality. The boundary and gradient operators in (3) are real linear maps.