OctoInformBeta

OpenAI preprint, September 2026 · Section 2. Plane trees and the triangulation statement

Lemma 2.1 [Complementary tree and forest duality]: For a finite edge set in a simple dual network, under real cycle-cut duality

A dual forest leaves a connected complement.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

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 NN with vertex set VV and edge set EE assigns to each edge e∈Ee\in E a tail tN(e)∈Vt_N(e)\in V and a head hN(e)∈Vh_N(e)\in V.✦ Let DD be a second network, with vertex set WW and the same edge set EE.

The underlying simple graph GNG_N of NN is the simple graph on VV in which distinct vertices are adjacent when some edge of NN has those endpoints, in either order.✦ For a map j:K→Ej:K\to E, the edge restriction N|jN|_j is the network on vertex set VV and edge set KK whose edge kk has tail tN(j(k))t_N(j(k)) and head hN(j(k))h_N(j(k)).✦ For F⊆EF\subseteq E, write N|FN|_F for the restriction along the inclusion F→EF\to E.

A simple network NN is a directed multigraph whose edges have distinct endpoints and whose map e↦{tN(e),hN(e)}e\mapsto\{t_N(e),h_N(e)\} to unordered endpoint pairs is injective.✦

Cycle and Cut Spaces

The oriented incidence matrix BNB_N of NN is the real matrix with rows indexed by VV and columns indexed by EE whose entries are given by (1). BN(v,e)=𝟏hN(e)=v−𝟏tN(e)=v.B_N(v,e)=\mathbf{1}_{h_N(e)=v}-\mathbf{1}_{t_N(e)=v}.(1)✦ The boundary operator ∂N:ℝE→ℝV\partial_N:\mathbb{R}^E\to\mathbb{R}^V is the map sending real edge weights to their signed net inflows at vertices.✦ The gradient operator ∇N:ℝV→ℝE\nabla_N:\mathbb{R}^V\to\mathbb{R}^E is the map sending a real vertex potential to its differences along directed edges.✦ Let xx denote real edge weights and ff a real vertex potential. ∂Nx=BNx,(∇Nf)(e)=f(hN(e))−f(tN(e)).\partial_N x=B_Nx, \qquad (\nabla_N f)(e)=f(h_N(e))-f(t_N(e)).(2)

The real cycle space ker⁡∂N\ker\partial_N of NN is the subspace of real edge weights with zero boundary, and the real cut space im⁡∇N\operatorname{im}\nabla_N of NN is the subspace of gradients of real vertex potentials. The networks NN and DD are in cycle-cut duality if GNG_N and GDG_D are connected and their spaces satisfy (3). ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\ker\partial_N=\operatorname{im}\nabla_D, \qquad \ker\partial_D=\operatorname{im}\nabla_N.(3)✦

The Claim

Theorem 1. Let NN and DD be networks in cycle-cut duality, with DD simple. Let S⊆ES\subseteq E be a finite edge set such that GD|SG_{D|_S} is acyclic. Then GN|E\S is connected.G_{N|_{E\setminus S}}\text{ is connected}.(4)✦

In the paper, the result reads: for a connected graph NN embedded on the sphere, the duals of the edges outside a spanning tree of NN form a spanning tree of D=N*D=N^*, and, more generally, the duals of the edges outside a spanning forest of NN form a connected spanning subgraph of DD.

What Is Checked

The statement (4) concerns edge restrictions of networks NN and DD in cycle-cut duality, with DD simple and GD|SG_{D|_S} acyclic for a finite set S⊆ES\subseteq E. The boundary and gradient operators are real linear maps.