The Setting
An acyclic edge set in one network can be deleted from another network on the same edge set. The question is whether the remaining spanning graph is connected.
A directed multigraph with vertex set and edge set assigns to each edge a tail and a head .✦ Let be a second network, with vertex set and the same edge set .
The underlying simple graph of is the simple graph on in which distinct vertices are adjacent when some edge of has those endpoints, in either order.✦ For a map , the edge restriction is the network on vertex set and edge set whose edge has tail and head .✦ For , write for the restriction along the inclusion .
A simple network is a directed multigraph whose edges have distinct endpoints and whose map to unordered endpoint pairs is injective.✦
Cycle and Cut Spaces
The oriented incidence matrix of is the real matrix with rows indexed by and columns indexed by whose entries are given by (1). (1)✦ The boundary operator is the map sending real edge weights to their signed net inflows at vertices.✦ The gradient operator is the map sending a real vertex potential to its differences along directed edges.✦ Let denote real edge weights and a real vertex potential. (2)
The real cycle space of is the subspace of real edge weights with zero boundary, and the real cut space of is the subspace of gradients of real vertex potentials. The networks and are in cycle-cut duality if and are connected and their spaces satisfy (3). (3)✦
The Claim
Theorem 1. Let and be networks in cycle-cut duality, with simple. Let be a finite edge set such that is acyclic. Then (4)✦
In the paper, the result reads: for a connected graph embedded on the sphere, the duals of the edges outside a spanning tree of form a spanning tree of , and, more generally, the duals of the edges outside a spanning forest of form a connected spanning subgraph of .
What Is Checked
The statement (4) concerns edge restrictions of networks and in cycle-cut duality, with simple and acyclic for a finite set . The boundary and gradient operators are real linear maps.