OctoInformBeta

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

§2 (setting): plane duality and the triangulation: Network definitions for colored triangulations and cuts of size three

Connected finite plane graphs admit exact duals.

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

Plane duality asks for a second network on the same edge set as a given plane graph. Real edge weights allow the relation between cycles and cuts to be stated through boundary and gradient maps.

Let VV, WW and EE be finite sets.

Definition 1. A directed network NN with vertex set VV and edge set EE is a pair of maps assigning a tail and a head to each edge, as in (1): tail⁡N,head⁡N:E→V.\operatorname{tail}_N,\operatorname{head}_N:E\longrightarrow V.(1)✦

Write DD for a network with vertex set WW and the same edge set EE.

The underlying simple graph GNG_N has vertex set VV; two distinct vertices are adjacent when some edge of NN has them as its endpoints.✦ A simple network NN is a network in which every edge has distinct endpoints and no two edges have the same unordered pair of endpoints.✦ A network NN on VV and the edge set E(G)E(G) of a simple graph GG realizes GG when the endpoints of each edge agree with those of that edge in GG, as in (2): {tail⁡N(e),head⁡N(e)}=e(e∈E(G)).\{\operatorname{tail}_N(e),\operatorname{head}_N(e)\}=e \qquad(e\in E(G)).(2)✦

An edge ee of NN is incident with v∈Vv\in V when vv is its tail or its head.✦ The star st⁡N(v)\operatorname{st}_N(v) of a vertex v∈Vv\in V in NN is the set of edges of NN incident with vv.✦ For A⊆VA\subseteq V, the edge cut δN(A)\delta_N(A) is the set of edges with exactly one endpoint in AA, given by (3): δN(A)={e∈E:|{tail⁡N(e),head⁡N(e)}∩A|=1,tail⁡N(e)≠head⁡N(e)}.\delta_N(A)=\{e\in E: |\{\operatorname{tail}_N(e),\operatorname{head}_N(e)\}\cap A|=1, \ \operatorname{tail}_N(e)\ne\operatorname{head}_N(e)\}.(3)✦

A triangle TT of NN on S⊆ES\subseteq E is an ordered triple of distinct corners viv_i and distinct edges eie_i, indexed by i∈ℤ/3ℤi\in\mathbb Z/3\mathbb Z, satisfying (4): {e0,e1,e2}=S,{tail⁡N(ei),head⁡N(ei)}={vi,vi+1}.\{e_0,e_1,e_2\}=S,\qquad \{\operatorname{tail}_N(e_i),\operatorname{head}_N(e_i)\} =\{v_i,v_{i+1}\}.(4)✦

Edge Spaces and Duality

The oriented incidence matrix BNB_N of the network NN is the matrix with rows indexed by VV, columns indexed by EE and entries given in (5). The boundary map ∂N:ℝE→ℝV\partial_N:\mathbb R^E\to\mathbb R^V and the gradient map ∇N:ℝV→ℝE\nabla_N:\mathbb R^V\to\mathbb R^E are the linear maps defined with it by (5), where 𝟏P\mathbf 1_P is 11 when PP holds and 00 otherwise: BN(v,e)=𝟏head⁡N(e)=v−𝟏tail⁡N(e)=v,∂Nz=BNz,(∇Nf)(e)=f(head⁡N(e))−f(tail⁡N(e)).\begin{aligned} B_N(v,e)&=\mathbf 1_{\operatorname{head}_N(e)=v} -\mathbf 1_{\operatorname{tail}_N(e)=v},\\ \partial_N z&=B_Nz,\\ (\nabla_N f)(e)&=f(\operatorname{head}_N(e))-f(\operatorname{tail}_N(e)). \end{aligned}(5) For an edge e∈Ee\in E and a vertex v∈Vv\in V of NN, the outgoing edge sign ϵN(e,v)\epsilon_N(e,v) is the number given by (6): ϵN(e,v)={1,tail⁡N(e)=v,−1,tail⁡N(e)≠v.\epsilon_N(e,v)= \begin{cases} 1,&\operatorname{tail}_N(e)=v,\\ -1,&\operatorname{tail}_N(e)\ne v. \end{cases}(6) The corresponding definitions for DD use its vertex set WW.

Definition 2. A cycle-cut duality between NN and DD is the relation 𝒟(N,D)\mathcal D(N,D) defined by (7); the kernels are the spaces of real circulations: 𝒟(N,D):GN and GD are connected,ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\mathcal D(N,D):\quad \begin{gathered} G_N\text{ and }G_D\text{ are connected},\\ \ker\partial_N=\operatorname{im}\nabla_D,\qquad \ker\partial_D=\operatorname{im}\nabla_N. \end{gathered}(7)✦

A plane embedding of a finite simple graph GG is a placement of its vertices at distinct points of ℝ2\mathbb R^2 with an injective continuous arc for each ordered adjacent pair. The arc runs between the corresponding vertex points, and reversing the pair reverses the arc. Each arc meets vertex points only at its endpoints, and interiors of arcs for distinct unoriented edges are disjoint.

The Claim

Definition 3. A colored triangulation duality between NN and DD consists of a black vertex set B⊆VB\subseteq V and triples Tv=(wv,i,ev,i)i∈ℤ/3ℤT_v=(w_{v,i},e_{v,i})_{i\in\mathbb Z/3\mathbb Z} for v∈Vv\in V satisfying (8). Here 𝟏U\mathbf 1_U denotes the indicator function of U⊆VU\subseteq V. 𝒟(N,D),N,D are simple,deg⁡GN(v)=3(v∈V),𝟏B(tail⁡N(e))+𝟏B(head⁡N(e))=1(e∈E),Tv is a triangle of D on st⁡N(v)(v∈V),(∇N𝟏{v})(ev,i)=ϵD(ev,i,wv,i)(v∈V,i∈ℤ/3ℤ).\begin{gathered} \mathcal D(N,D),\qquad N,D\text{ are simple},\qquad \deg_{G_N}(v)=3\quad(v\in V),\\ \mathbf 1_B(\operatorname{tail}_N(e))+ \mathbf 1_B(\operatorname{head}_N(e))=1\quad(e\in E),\\ T_v\text{ is a triangle of }D\text{ on }\operatorname{st}_N(v) \quad(v\in V),\\ (\nabla_N\mathbf 1_{\{v\}})(e_{v,i})= \epsilon_D(e_{v,i},w_{v,i}) \quad(v\in V,\ i\in\mathbb Z/3\mathbb Z). \end{gathered}(8)✦

Definition 4. A finite network NN is three-edge-connected when every nonempty proper vertex subset has at least three edges in its cut, as in (9): |δN(A)|≥3(⌀≠A⊊V).|\delta_N(A)|\geq 3\qquad(\varnothing\ne A\subsetneq V).(9)✦ A finite network NN has only trivial three-edge cuts when every cut of size three separates off a single vertex, as in (10): |A|=1or|V\A|=1(A⊆V,|δN(A)|=3).|A|=1\ \text{or}\ |V\setminus A|=1 \qquad(A\subseteq V,\ |\delta_N(A)|=3).(10)✦

Theorem 1. Let GG be a connected finite simple graph with a plane embedding and vertex set VV. There exist networks with the properties in (11): ∃W finite,N on (V,E(G)),D on (W,E(G)):N realizes G,𝒟(N,D).\begin{gathered} \exists\, W\text{ finite},\quad N\text{ on }(V,E(G)),\quad D\text{ on }(W,E(G)):\\ N\text{ realizes }G,\qquad \mathcal D(N,D). \end{gathered}(11)✦

In the paper, the result reads: a sphere triangulation DD is connected and simple, has at least four vertices, and has a 33-cycle as every face boundary; its faces are black and white, with opposite colors across every edge; a separating triangle has vertices strictly on both sides; a spanning forest includes all vertices, with isolated vertices allowed, and a one-vertex graph is a tree; intermediate plane graphs may have loops and parallel edges, with boundary lengths counting edge-side incidences.

What Is Checked

The network definitions concern finite vertex and edge sets; the exact dual existence statement concerns a connected finite simple graph equipped with a plane embedding.