The Setting
Plane duality asks for a second network on the same edge set as a given plane graph. Real edge weights allow the relation between cycles and cuts to be stated through boundary and gradient maps.
Let , and be finite sets.
Definition 1. A directed network with vertex set and edge set is a pair of maps assigning a tail and a head to each edge, as in (1): (1)✦
Write for a network with vertex set and the same edge set .
The underlying simple graph has vertex set ; two distinct vertices are adjacent when some edge of has them as its endpoints.✦ A simple network is a network in which every edge has distinct endpoints and no two edges have the same unordered pair of endpoints.✦ A network on and the edge set of a simple graph realizes when the endpoints of each edge agree with those of that edge in , as in (2): (2)✦
An edge of is incident with when is its tail or its head.✦ The star of a vertex in is the set of edges of incident with .✦ For , the edge cut is the set of edges with exactly one endpoint in , given by (3): (3)✦
A triangle of on is an ordered triple of distinct corners and distinct edges , indexed by , satisfying (4): (4)✦
Edge Spaces and Duality
The oriented incidence matrix of the network is the matrix with rows indexed by , columns indexed by and entries given in (5). The boundary map and the gradient map are the linear maps defined with it by (5), where is when holds and otherwise: (5) For an edge and a vertex of , the outgoing edge sign is the number given by (6): (6) The corresponding definitions for use its vertex set .
Definition 2. A cycle-cut duality between and is the relation defined by (7); the kernels are the spaces of real circulations: (7)✦
A plane embedding of a finite simple graph is a placement of its vertices at distinct points of with an injective continuous arc for each ordered adjacent pair. The arc runs between the corresponding vertex points, and reversing the pair reverses the arc. Each arc meets vertex points only at its endpoints, and interiors of arcs for distinct unoriented edges are disjoint.
The Claim
Definition 3. A colored triangulation duality between and consists of a black vertex set and triples for satisfying (8). Here denotes the indicator function of . (8)✦
Definition 4. A finite network is three-edge-connected when every nonempty proper vertex subset has at least three edges in its cut, as in (9): (9)✦ A finite network has only trivial three-edge cuts when every cut of size three separates off a single vertex, as in (10): (10)✦
Theorem 1. Let be a connected finite simple graph with a plane embedding and vertex set . There exist networks with the properties in (11): (11)✦
In the paper, the result reads: a sphere triangulation is connected and simple, has at least four vertices, and has a -cycle as every face boundary; its faces are black and white, with opposite colors across every edge; a separating triangle has vertices strictly on both sides; a spanning forest includes all vertices, with isolated vertices allowed, and a one-vertex graph is a tree; intermediate plane graphs may have loops and parallel edges, with boundary lengths counting edge-side incidences.
What Is Checked
The network definitions concern finite vertex and edge sets; the exact dual existence statement concerns a connected finite simple graph equipped with a plane embedding.