OctoInformBeta

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

Theorem 2.2 [Prescribed induced-tree partition]: With connected spanning complements in simple cubic bipartite networks admitting cycle cut duality and three-edge connectivity

Perfect matchings through any prescribed edge.

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

Which edges can be prescribed in a perfect matching when its complementary spanning graph must be connected?

A finite network NN with vertex set VV and edge set EE is a pair of finite sets together with maps assigning a tail and a head in VV to every edge in EE.✦ The underlying simple graph G(N)G(N) of a finite network NN with vertex set VV is the simple graph on VV in which distinct vertices are adjacent when they are the endpoints of an edge of NN.✦ A finite network NN is simple when it has no loops and each unordered pair of endpoints determines at most one edge.✦ Let DD be a second finite network, with vertex set FF and the same edge set EE.

An edge is incident to a vertex when that vertex is its tail or its head.✦ The vertex star SN(v)S_N(v) of a vertex v∈Vv\in V in NN is the set of edges of NN incident to vv.✦ A perfect matching PP of NN is a subset of EE that meets every vertex star in exactly one edge. The edge restriction N|jN|_j along a map j:K→Ej:K\to E is the network on VV with edge set KK and endpoints given by composing jj with the endpoint maps of NN.✦ For an edge subset H⊆EH\subseteq E, write N|HN|_H for restriction along its inclusion.

The edge cut δN(U)\delta_N(U) of a vertex set U⊆VU\subseteq V consists of the edges with exactly one endpoint in UU.✦ A finite network NN is three-edge-connected when every edge cut of NN with two nonempty shores has at least three edges.✦ A finite network NN has trivial three-edge cuts when every edge cut of NN of size three has a singleton shore.✦

For real edge weights zz and vertex potentials ff, the oriented incidence matrix BNB_N, its linear boundary operator ∂N\partial_N, and the linear gradient operator ∇N\nabla_N are defined by (1), where 𝟏\mathbf1 denotes an indicator; use the analogous notation for DD. (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} &=\mathbf1_{\{\operatorname{head}_N(e)=v\}} -\mathbf1_{\{\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}(1)

A cycle cut duality between NN and DD means that G(N)G(N) and G(D)G(D) are connected and their real cycle and cut spaces satisfy (2). ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\ker\partial_N=\operatorname{im}\nabla_D, \qquad \ker\partial_D=\operatorname{im}\nabla_N.(2)✦

The Triangle States

A triangle tt in DD on an edge set HH consists of cyclic lists of distinct corners ct(i)c_t(i) and distinct edges at(i)a_t(i), indexed by i∈ℤ/3ℤi\in\mathbb Z/3\mathbb Z, with edge set HH and with at(i)a_t(i) joining ct(i)c_t(i) to ct(i+1)c_t(i+1).✦ The outgoing edge sign ϵD(e,x)\epsilon_D(e,x) is +1+1 when x=tail⁡D(e)x=\operatorname{tail}_D(e) and −1-1 otherwise.✦

A colored triangulation duality MM between NN and DD is a cycle cut duality in which NN is simple and cubic, DD is simple, and a black class B⊆VB\subseteq V contains exactly one endpoint of each edge of NN. A colored triangulation duality MM between NN and DD assigns to each v∈Vv\in V a triangle tvt_v in DD on the edge set SN(v)S_N(v). For the vertex indicator 𝟏{v}\mathbf1_{\{v\}}, the orientation compatibility required of these triangles is (3). (∇N𝟏{v})(atv(i))=ϵD(atv(i),ctv(i))(v∈V,i∈ℤ/3ℤ).\bigl(\nabla_N\mathbf1_{\{v\}}\bigr)(a_{t_v}(i)) =\epsilon_D(a_{t_v}(i),c_{t_v}(i)) \qquad(v\in V,\ i\in\mathbb Z/3\mathbb Z).(3)

A triangle system on FF is an indexed family of triples of distinct vertices in which each unordered pair of vertices occurs in at most one member.✦ Choose a black root triangle t0=tv0t_0=t_{v_0}, with v0∈Bv_0\in B. Let AA be the other black triangles, indexed by B\{v0}B\setminus\{v_0\}, and let XX be the vertices outside the three corners of t0t_0. The triangles indexed by AA, with their corners ct(i)c_t(i), form the black face triangle system.✦

A state ss on XX is a bijection s:A→Xs:A\to X selecting a corner s(t)s(t) of each triangle tt.✦ Two states r,sr,s on XX are partners when r(t)≠s(t)r(t)\ne s(t) for every t∈At\in A.✦ A paired state (r,s)(r,s) on XX is an ordered pair of partner states on XX, with ss its second state. The opposite edge graph QsQ_s is the simple graph on FF whose edges are the sides of the triangles t∈At\in A opposite their selected corners s(t)s(t).✦

The Claim

Theorem 1. Let MM be a colored triangulation duality between NN and DD, with a black root triangle t0t_0. Suppose (r,s)(r,s) is a paired state on XX and QsQ_s is acyclic. For every side ei=at0(i)e_i=a_{t_0}(i) of t0t_0, there is a set P⊆EP\subseteq E satisfying (4). ei∈P,|P∩SN(v)|=1(v∈V),G(N|E\P) is connected.e_i\in P,\qquad |P\cap S_N(v)|=1\quad(v\in V),\qquad G(N|_{E\setminus P})\text{ is connected}.(4)✦

Let MM be a colored triangulation duality between NN and DD. Suppose NN is three-edge-connected and its three-edge cuts are trivial. For every e∈Ee\in E, there is a set P⊆EP\subseteq E satisfying (5). e∈P,|P∩SN(v)|=1(v∈V),G(N|E\P) is connected.e\in P,\qquad |P\cap S_N(v)|=1\quad(v\in V),\qquad G(N|_{E\setminus P})\text{ is connected}.(5)✦

Let NN be simple, cubic and three-edge-connected, with a bipartition B⊆VB\subseteq V, and suppose NN and DD form a cycle cut duality. For every e∈Ee\in E, there is a set P⊆EP\subseteq E satisfying (6). e∈P,|P∩SN(v)|=1(v∈V),G(N|E\P) is connected.e\in P,\qquad |P\cap S_N(v)|=1\quad(v\in V),\qquad G(N|_{E\setminus P})\text{ is connected}.(6)✦

In the paper, the result reads: if DD is a sphere triangulation with black and white faces such that each edge has one incident face of each color, then, for any facial triangle t0t_0 and any edge e0e_0 of t0t_0, FF admits a partition into two sets each inducing a tree, with the endpoints of e0e_0 in one set and the third corner of t0t_0 in the other.

What Is Checked

Statement (4) is over a colored triangulation duality with a black root and paired states with QsQ_s acyclic; (5) is over a colored triangulation duality with three-edge connectivity and trivial three-edge cuts; and (6) is over a simple cubic bipartite network with three-edge connectivity and a cycle cut dual.