The Setting
Let be a finite cubic network on and its dual triangulation on , with shared edge set . A directed network is a network with a specified tail and head for each edge.✦ The underlying simple graph of the network is the graph on joining distinct vertices when an edge of has those endpoints.✦ A simple network is a network with no loops and at most one edge with any given unordered pair of endpoints.✦ For a vertex , the star of in is the set of edges incident to ✦; incidence means that is either endpoint.✦
For a network with vertex set , its oriented incidence matrix , boundary operator and gradient operator are given by (1), for a real edge weighting and vertex potential : (1) A cycle-cut duality between and means that both underlying graphs are connected and their real cycle and cut spaces satisfy (2): (2)✦
A colored triangulation duality between and is a cycle-cut duality with simple and cubic, simple, and a black class containing exactly one endpoint of every edge. The triangles indexed by are white. Each has a dual triangle whose distinct corners and distinct sides are cyclically indexed by . The side joins to , and the three sides are exactly . For an edge and a vertex of , the outgoing sign is the sign if is the tail of in , and otherwise.✦ The triangles satisfy the orientation compatibility (3): (3) For distinct indices , write for the side joining to ; it is when , and otherwise.✦
Fix a root triangle . The nonroot black triangles and the dual vertices outside the corners of the root triangle are the sets in (4): (4) A triangle system on is a family of injective three-corner maps indexed by in which two triangles sharing two distinct corners have the same index.✦ The black triangles indexed by form a triangle system with corner maps .✦
States and Selected Networks
A state of the black triangle system is a choice of a corner index for each such that its selected-corner map in (5) is a bijection onto : (5) A paired state is an ordered pair of states with for every .✦ The opposite edge graph is the simple graph on consisting of the sides of the black triangles opposite their selected corners .✦
For corner indices , the third index is their negative sum modulo three; when , it is the remaining index.✦ For a paired state and a triangle , the first-to-third side of is the side specified in (6): (6) For a root index , the root-augmented side labelling is the map from to in (7); its image is the removed edge set : (7) All root corner indices in (7) are taken modulo three. The consecutive root corner indices based at are and , taken modulo three.
A perfect matching of is an edge set meeting each vertex star exactly once. Write for the family defined in (8), and for the unique matching edge incident to when : (8) For an edge and a vertex of , the opposite-end map is when , and otherwise.✦ For a state and , the selected corner network is the directed network on with edge set and endpoints prescribed by (9): (9)✦ A perfect matching of is compatible with a state of the black triangle system when the incidence condition (10) holds: (10)
For a map , the edge restriction of along is the directed network on with edge set in which each edge has the endpoints of in .✦ When is the inclusion of an edge subset , write this restriction as .
The Claim
Theorem 1. Let and have the colored triangulation duality described above. For a state and a perfect matching compatible with , (11)✦ If, in addition, the root is black and its matching edge is the prescribed side , then (12)✦ For a black root , a paired state with a forest, and any root index , there is a perfect matching as in (13): (13)✦
In the paper, the result reads: if has no separating triangle, choose a pair with a forest, form the tree on white triangles by the complementary incidence-spoke construction, root it across the prescribed outer edge , and select one edge at each black and white triangle as in Section 6, including ; the resulting selected set is a forest.
What Is Checked
Statements (11) and (12) concern finite colored cycle-cut dualities, states and perfect matchings satisfying (10), with a black root and prescribed root matching side for (12); statement (13) concerns the removed edge sets of paired states at a black root with a forest.