The Setting
Can two sides of a root triangle be adjoined to selected sides of the black triangles without creating a cycle? The setting is a cubic bipartite network and its dual triangulation.
Let be a network on a vertex set , and let be a network on a vertex set , with common edge set . A network on a vertex set with edge set is an assignment of a tail and a head in to every edge in .✦ The underlying simple graph of a network on is the simple graph on that joins distinct vertices whenever an edge of has those endpoints.✦ A simple network is a network with no loops in which each unordered endpoint pair determines at most one edge.✦ An edge of a network is incident with a vertex of when is the tail or head of ✦; the star at in is the set of edges of incident with .✦
For a network , the oriented incidence matrix , boundary operator on real edge weights , and gradient operator on real vertex potentials are given by (1). (1) A cycle-cut duality is a pair of networks with a common edge set whose underlying graphs are connected and whose real cycle and cut spaces satisfy (2). (2)✦
A triangle on an edge set is a configuration of three distinct corners and three distinct edges , indexed cyclically by , where the edges exhaust and joins to .✦ A colored triangulation duality is a cycle-cut duality in which and are simple, is cubic, and a black vertex class gives a bipartite coloring. For each , there is a triangle of with edge set the star of in ; write its corners and edges as and .
For an edge and a vertex of , the outgoing edge sign is the sign when is the tail of in , and otherwise.✦ The triangles in a colored triangulation duality satisfy the orientation compatibility in (3), where is the potential equal to one at and zero elsewhere. (3)
Corner Choices and Root Edges
Fix a root vertex and call its dual triangle the root triangle. The nonroot black triangles are indexed by , and the nonroot dual vertices form , as in (4). (4) A triangle system on is a family of injective corner maps in which two triangles sharing two distinct corners have the same index.✦ The black face triangle system at is the triangle system on whose corner maps are those of the dual triangles indexed by .✦
A state onto is a choice of one corner index for each such that its selected vertex map is a bijection onto , as specified in (5).✦ Such a state is a triangle transversal. (5) Paired states are an ordered pair of triangle transversals onto that are pointwise distinct: for every .✦ The opposite edge graph is the simple graph on whose edges are the sides opposite the choices of , given by (6). (6)✦
The third corner index , calculated modulo three, is the remaining index when , and their common index when .✦ For paired states , the third corner network is the network on with edge set and endpoints given by (7). (7)✦
The two-edge sink extension of a network on , with starting vertices and target , is the network on that retains the edges of and adjoins two distinct edges and .✦ For a root index , the consecutive starting indices are for .✦ For paired states and a root index , the root-augmented network is the network on obtained from by adjoining the two edges specified by (8); all corner indices are taken modulo three. (8)✦
The Claim
Theorem 1. Let be paired states onto , and suppose that is a forest. For every root index , (9)✦
In the paper, the result reads: for a pair with a forest, every component of contains exactly one of the three root corners.
What Is Checked
The statement (9) is over a colored triangulation duality, its black face triangle system at , paired transversals of the nonroot dual vertices , and a root index , under the hypothesis that is a forest. The boundary and gradient operators are linear.