OctoInformBeta

OpenAI preprint, September 2026 · Section 7. Separating triangles and the Hamiltonian cycle

§7 (proof setting): gluing the prescribed selection: Three-edge cuts and the choice of a prescribed matching edge with connected complement

Compatible capped matchings glue together.

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

The objects are perfect matchings on the two shores of an edge cut, after each shore has been capped by a new vertex. Connectivity of the edges outside the matching is the global constraint, together with the inclusion of a prescribed edge.

A finite network NN is a directed multigraph with vertex set VV, edge set EE, and tail and head maps t,h:E→Vt,h:E\to V.✦ Its underlying simple graph G(N)G(N) joins distinct vertices when some edge of NN has those endpoints, in either order.✦ A simple network NN is a network with no loops and at most one edge with any given unordered pair of endpoints.✦ A cubic network NN is a network whose underlying graph has degree three at every vertex.

An edge ee is incident with a vertex vv when t(e)=vt(e)=v or h(e)=vh(e)=v.✦ The vertex star st⁡N(v)\operatorname{st}_N(v) of a vertex vv in NN is the set of edges of NN incident with vv, as in (1). st⁡N(v)={e∈E:t(e)=v or h(e)=v}.\operatorname{st}_N(v)=\{e\in E:t(e)=v\text{ or }h(e)=v\}.(1)✦ A perfect matching MM of NN is a set of edges satisfying (2). |M∩st⁡N(v)|=1(v∈V).|M\cap\operatorname{st}_N(v)|=1\qquad(v\in V).(2)

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 endpoint maps t∘j,h∘jt\circ j,h\circ j.✦ For F⊆EF\subseteq E, write N[F]N[F] for restriction along inclusion, and write N−M=N[E\M]N-M=N[E\setminus M].

Cuts and Capping

The edge cut δN(A)\delta_N(A) of A⊆VA\subseteq V in NN is the set of edges with exactly one endpoint in AA.✦ The region edge set EAE_A of a vertex set AA in NN is the set of edges of NN incident with AA, as in (3). δN(A)={e∈E:(t(e)∈A,h(e)∉A) or (h(e)∈A,t(e)∉A)},EA={e∈E:t(e)∈A or h(e)∈A}.\begin{aligned} \delta_N(A)&=\{e\in E:(t(e)\in A,\ h(e)\notin A) \text{ or }(h(e)\in A,\ t(e)\notin A)\},\\ E_A&=\{e\in E:t(e)\in A\text{ or }h(e)\in A\}. \end{aligned}(3) A three-edge-connected network NN is a network satisfying (4). |δN(A)|≥3(⌀≠A⊊V).|\delta_N(A)|\geq 3\qquad(\varnothing\ne A\subsetneq V).(4)✦

The vertex pushforward qNqN along a map q:V→Wq:V\to W is the network on WW with edge set EE and endpoint maps q∘t,q∘hq\circ t,q\circ h.✦ The capping map κA\kappa_A of a vertex set AA in NN is a map that fixes each vertex of AA and sends every vertex outside AA to a new vertex *A*_A.✦ The capped network NAN_A of a vertex set AA in NN is the network obtained by retaining the edges EAE_A in the vertex pushforward along the capping map κA\kappa_A, as in (5). κA:V→A∪{*A},κA(v)={v,v∈A,*A,v∉A,NA=(κAN)[EA].\kappa_A:V\longrightarrow A\cup\{*_A\},\qquad \kappa_A(v)= \begin{cases} v,&v\in A,\\ *_A,&v\notin A, \end{cases} \qquad N_A=(\kappa_A N)[E_A].(5) Perfect matchings PP of NAN_A and QQ of NAcN_{A^c}, where AcA^c denotes the complement of AA in VV, are compatible when their choices agree on the cut, in the sense of (6); their edges are regarded as edges of NN. P∩δN(A)=Q∩δN(A).P\cap\delta_N(A)=Q\cap\delta_N(A).(6)

Cycle Cut Duality

Let DD be another finite network, with the same edge set EE. The oriented incidence matrix INI_N has the entries in (7). IN(v,e)=𝟏h(e)=v−𝟏t(e)=v.I_N(v,e)=\mathbf{1}_{h(e)=v}-\mathbf{1}_{t(e)=v}.(7)✦ For edge weights x∈ℝEx\in\mathbb{R}^E and potentials f∈ℝVf\in\mathbb{R}^V, the boundary operator ∂N:ℝE→ℝV\partial_N:\mathbb{R}^E\to\mathbb{R}^V and the gradient ∇N:ℝV→ℝE\nabla_N:\mathbb{R}^V\to\mathbb{R}^E are the linear maps in (8), giving signed net inflows and differences across edges, respectively. ∂Nx=INx,(∇Nf)(e)=f(h(e))−f(t(e)).\partial_N x=I_Nx,\qquad (\nabla_N f)(e)=f(h(e))-f(t(e)).(8) The cycle space of NN is the subspace ker⁡∂N\ker\partial_N and the cut space of NN is the subspace im⁡∇N\operatorname{im}\nabla_N, with the corresponding notation for DD. Networks NN and DD are in cycle cut duality when both underlying graphs are connected and (9) holds. ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\ker\partial_N=\operatorname{im}\nabla_D,\qquad \ker\partial_D=\operatorname{im}\nabla_N.(9)✦

A bipartition class B⊆VB\subseteq V is a set containing exactly one endpoint of every edge of NN.

The Claim

Theorem 1. Let A⊆VA\subseteq V, and let P,QP,Q be compatible perfect matchings of NA,NAcN_A,N_{A^c}, respectively, and set R=P∪QR=P\cup Q. Then (10) holds. |R∩st⁡N(v)|=1(v∈V).|R\cap\operatorname{st}_N(v)|=1\qquad(v\in V).(10)✦ Suppose also that NN is simple, cubic and three-edge-connected, that |δN(A)|=3|\delta_N(A)|=3, and that |A|,|Ac|≥2|A|,|A^c|\geq2. If G(NA−P)G(N_A-P) and G(NAc−Q)G(N_{A^c}-Q) are connected, then (11) holds. G(N−R) is connected.G(N-R)\text{ is connected}.(11)✦ Let NN be a simple cubic three-edge-connected network with a bipartition class BB, and let DD be in cycle cut duality with NN. For every prescribed edge e∈Ee\in E, there is a set M⊆EM\subseteq E satisfying (12). e∈M,|M∩st⁡N(v)|=1(v∈V),G(N−M) is connected.e\in M,\qquad |M\cap\operatorname{st}_N(v)|=1\ (v\in V),\qquad G(N-M)\text{ is connected}.(12)✦

In the paper, the result reads: split a separating triangle of DD, cap each piece, prescribe the same selected cap side in both pieces, and glue the induced trees along either one vertex or an edge, preserving the original prescription.

What Is Checked

The gluing assertions are stated over capped networks and their edge restrictions, with compatibility on the cut, whereas the prescribed-edge assertion is stated over cycle cut duality and a bipartition of a simple cubic three-edge-connected network.