The Setting
The question is whether two selections of corners in black triangles can differ in every triangle while each covers every vertex outside a root triangle exactly once.
A network on finite vertex and edge sets and is a directed multigraph assigning a tail and a head to each edge.✦ Let be a second network, with vertex set and the same edge set . The underlying simple graph of a network joins distinct vertices when they are endpoints of an edge.✦ A network is simple when it has no loops and no two edges have the same unordered pair of endpoints.✦ An edge is incident to a vertex when is its tail or head; the star is the set of edges incident to .
The oriented incidence matrix has rows indexed by and columns indexed by . The boundary operator sends real edge weights to their signed net inflows, and the gradient operator sends real vertex potentials to edge weights, with their values given by (1). (1)
A cycle cut duality between and means that their underlying graphs are connected and their real cycle and cut spaces satisfy (2). (2)✦
A triangle in on an edge set is a configuration of three distinct corners and three distinct edges whose set is , with joining to ; indices are taken modulo three.✦ A colored triangulation duality between networks and is a cycle cut duality between them in which is simple and cubic and is simple, together with a black vertex class containing exactly one endpoint of each edge, and a triangle in on for each . Write and for its corners and sides. For an edge and a vertex of , the outgoing edge sign is when is the tail of in , and otherwise.✦ The triangles satisfy the orientation compatibility condition (3). (3)
Fix a black vertex and its root triangle . The other black triangles are indexed by , and is the set of dual vertices outside the root corners, as in (4). (4)
States and Cut Conditions
A triangle system on indexed by is a family of injective corner maps in which a pair of distinct vertices belongs to at most one triangle.✦ For the black triangles indexed by , write for the corner set of .
A state on is a choice of one corner in each triangle whose selected vertices give a bijection from to .✦ Write for the selected vertex of triangle , and for the set of states in (5). (5)✦ Two states on are partners, or disjoint states, when for every .✦ A pair on is an ordered pair of partner states on ; let be the set of pairs.✦
The edge cut of a vertex set is the set of edges with exactly one endpoint in .✦ The network is three-edge-connected when every nonempty proper vertex set has an edge cut of size at least three.✦ The three-edge cuts of are trivial when every vertex set with an edge cut of size three is a singleton or has a singleton complement.✦
The Claim
Theorem 1. Let and have a colored triangulation duality, and let be a black root triangle. Suppose that is three-edge-connected and that all its three-edge cuts are trivial. For every , (6)✦ Moreover, (7)✦
What Is Checked
The capacity bound (6) and the existence statement (7) are stated over a finite colored triangulation duality with a black root and the two cut conditions on . The corner maps of the black triangles indexed by form a triangle system.✦