The Setting
The objects are perfect matchings on the two shores of an edge cut, after each shore has been capped by a new vertex. Connectivity of the edges outside the matching is the global constraint, together with the inclusion of a prescribed edge.
A finite network is a directed multigraph with vertex set , edge set , and tail and head maps .✦ Its underlying simple graph joins distinct vertices when some edge of has those endpoints, in either order.✦ A simple network is a network with no loops and at most one edge with any given unordered pair of endpoints.✦ A cubic network is a network whose underlying graph has degree three at every vertex.
An edge is incident with a vertex when or .✦ The vertex star of a vertex in is the set of edges of incident with , as in (1). (1)✦ A perfect matching of is a set of edges satisfying (2). (2)
The edge restriction along a map is the network on with edge set and endpoint maps .✦ For , write for restriction along inclusion, and write .
Cuts and Capping
The edge cut of in is the set of edges with exactly one endpoint in .✦ The region edge set of a vertex set in is the set of edges of incident with , as in (3). (3) A three-edge-connected network is a network satisfying (4). (4)✦
The vertex pushforward along a map is the network on with edge set and endpoint maps .✦ The capping map of a vertex set in is a map that fixes each vertex of and sends every vertex outside to a new vertex .✦ The capped network of a vertex set in is the network obtained by retaining the edges in the vertex pushforward along the capping map , as in (5). (5) Perfect matchings of and of , where denotes the complement of in , are compatible when their choices agree on the cut, in the sense of (6); their edges are regarded as edges of . (6)
Cycle Cut Duality
Let be another finite network, with the same edge set . The oriented incidence matrix has the entries in (7). (7)✦ For edge weights and potentials , the boundary operator and the gradient are the linear maps in (8), giving signed net inflows and differences across edges, respectively. (8) The cycle space of is the subspace and the cut space of is the subspace , with the corresponding notation for . Networks and are in cycle cut duality when both underlying graphs are connected and (9) holds. (9)✦
A bipartition class is a set containing exactly one endpoint of every edge of .
The Claim
Theorem 1. Let , and let be compatible perfect matchings of , respectively, and set . Then (10) holds. (10)✦ Suppose also that is simple, cubic and three-edge-connected, that , and that . If and are connected, then (11) holds. (11)✦ Let be a simple cubic three-edge-connected network with a bipartition class , and let be in cycle cut duality with . For every prescribed edge , there is a set satisfying (12). (12)✦
In the paper, the result reads: split a separating triangle of , cap each piece, prescribe the same selected cap side in both pieces, and glue the induced trees along either one vertex or an edge, preserving the original prescription.
What Is Checked
The gluing assertions are stated over capped networks and their edge restrictions, with compatibility on the cut, whereas the prescribed-edge assertion is stated over cycle cut duality and a bipartition of a simple cubic three-edge-connected network.