The Setting
Which edges can be prescribed in a perfect matching when its complementary spanning graph must be connected?
A finite network with vertex set and edge set is a pair of finite sets together with maps assigning a tail and a head in to every edge in .✦ The underlying simple graph of a finite network with vertex set is the simple graph on in which distinct vertices are adjacent when they are the endpoints of an edge of .✦ A finite network is simple when it has no loops and each unordered pair of endpoints determines at most one edge.✦ Let be a second finite network, with vertex set and the same edge set .
An edge is incident to a vertex when that vertex is its tail or its head.✦ The vertex star of a vertex in is the set of edges of incident to .✦ A perfect matching of is a subset of that meets every vertex star in exactly one edge. The edge restriction along a map is the network on with edge set and endpoints given by composing with the endpoint maps of .✦ For an edge subset , write for restriction along its inclusion.
The edge cut of a vertex set consists of the edges with exactly one endpoint in .✦ A finite network is three-edge-connected when every edge cut of with two nonempty shores has at least three edges.✦ A finite network has trivial three-edge cuts when every edge cut of of size three has a singleton shore.✦
For real edge weights and vertex potentials , the oriented incidence matrix , its linear boundary operator , and the linear gradient operator are defined by (1), where denotes an indicator; use the analogous notation for . (1)
A cycle cut duality between and means that and are connected and their real cycle and cut spaces satisfy (2). (2)✦
The Triangle States
A triangle in on an edge set consists of cyclic lists of distinct corners and distinct edges , indexed by , with edge set and with joining to .✦ The outgoing edge sign is when and otherwise.✦
A colored triangulation duality between and is a cycle cut duality in which is simple and cubic, is simple, and a black class contains exactly one endpoint of each edge of . A colored triangulation duality between and assigns to each a triangle in on the edge set . For the vertex indicator , the orientation compatibility required of these triangles is (3). (3)
A triangle system on is an indexed family of triples of distinct vertices in which each unordered pair of vertices occurs in at most one member.✦ Choose a black root triangle , with . Let be the other black triangles, indexed by , and let be the vertices outside the three corners of . The triangles indexed by , with their corners , form the black face triangle system.✦
A state on is a bijection selecting a corner of each triangle .✦ Two states on are partners when for every .✦ A paired state on is an ordered pair of partner states on , with its second state. The opposite edge graph is the simple graph on whose edges are the sides of the triangles opposite their selected corners .✦
The Claim
Theorem 1. Let be a colored triangulation duality between and , with a black root triangle . Suppose is a paired state on and is acyclic. For every side of , there is a set satisfying (4). (4)✦
Let be a colored triangulation duality between and . Suppose is three-edge-connected and its three-edge cuts are trivial. For every , there is a set satisfying (5). (5)✦
Let be simple, cubic and three-edge-connected, with a bipartition , and suppose and form a cycle cut duality. For every , there is a set satisfying (6). (6)✦
In the paper, the result reads: if is a sphere triangulation with black and white faces such that each edge has one incident face of each color, then, for any facial triangle and any edge of , admits a partition into two sets each inducing a tree, with the endpoints of in one set and the third corner of in the other.
What Is Checked
Statement (4) is over a colored triangulation duality with a black root and paired states with acyclic; (5) is over a colored triangulation duality with three-edge connectivity and trivial three-edge cuts; and (6) is over a simple cubic bipartite network with three-edge connectivity and a cycle cut dual.