OctoInformBeta

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

Corollary 7.1 [Avoiding any prescribed edge]: Connected complements for simple cubic bipartite three-edge-connected networks with a cycle cut duality

Perfect matchings with a 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

A network NN on finite vertex and edge sets VV and EE is a directed multigraph assigning each edge e∈Ee\in E a tail tail⁡N(e)\operatorname{tail}_N(e) and a head head⁡N(e)\operatorname{head}_N(e) in VV.✦ The underlying simple graph GNG_N of a network NN has vertex set VV; two distinct vertices are adjacent when they are the endpoints of an edge of NN.✦ A network NN is simple when it has no loops and at most one edge with any given unordered pair of endpoints.✦ A network NN is cubic when every vertex of its underlying simple graph GNG_N has degree three.

An edge ee of NN is incident to a vertex vv when vv is its tail or its head.✦ The vertex star st⁡N(v)\operatorname{st}_N(v) of a vertex vv in a network NN is the set of all edges of NN incident to vv.✦ A perfect matching PP of NN is a subset of EE satisfying (1). |st⁡N(v)∩P|=1(v∈V).\bigl|\operatorname{st}_N(v)\cap P\bigr|=1 \qquad (v\in V).(1)

For a map j:K→Ej:K\to E, the edge restriction N[j]N[j] is the network on vertex set VV and edge set KK with endpoints tail⁡N(j(k))\operatorname{tail}_N(j(k)) and head⁡N(j(k))\operatorname{head}_N(j(k)) for k∈Kk\in K.✦ For a subset F⊆EF\subseteq E, write N|FN|_F for restriction along the inclusion of FF into EE.

For a vertex set S⊆VS\subseteq V, the edge cut δN(S)\delta_N(S) is the set of edges with exactly one endpoint in SS.✦ A network NN is three-edge-connected when every nonempty proper vertex set satisfies (2). |δN(S)|≥3(⌀≠S⊊V).|\delta_N(S)|\geq 3 \qquad (\varnothing\ne S\subsetneq V).(2)✦

A black color class B⊆VB\subseteq V gives a bipartition of NN when every edge has exactly one endpoint in BB.

The oriented incidence matrix INI_N, boundary operator ∂N\partial_N, and gradient operator ∇N\nabla_N of NN are the real matrix and maps defined in (3); here xx is an edge weight and ff is a vertex potential. (IN)v,e=𝟏head⁡N(e)=v−𝟏tail⁡N(e)=v,∂N:ℝE→ℝV,∂Nx=INx,∇N:ℝV→ℝE,(∇Nf)(e)=f(head⁡N(e))−f(tail⁡N(e)).\begin{aligned} (I_N)_{v,e} &=\mathbf{1}_{\operatorname{head}_N(e)=v} -\mathbf{1}_{\operatorname{tail}_N(e)=v},\\ \partial_N:\mathbb{R}^{E}\longrightarrow\mathbb{R}^{V}, &\qquad \partial_N x=I_Nx,\\ \nabla_N:\mathbb{R}^{V}\longrightarrow\mathbb{R}^{E}, &\qquad (\nabla_N f)(e) =f(\operatorname{head}_N(e))-f(\operatorname{tail}_N(e)). \end{aligned}(3) The real cycle space of a network NN is the kernel of the boundary operator of NN; the real cut space of NN is the range of the gradient operator of NN. Cycle cut duality is the relation between a network NN and a network DD on a vertex set WW and the same edge set EE that holds when their underlying simple graphs GNG_N and GDG_D are connected and satisfy (4). ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\ker\partial_N=\operatorname{im}\nabla_D, \qquad \ker\partial_D=\operatorname{im}\nabla_N.(4)✦

A Hamiltonian cycle in a simple graph GG is a closed walk in GG based at a vertex vv that visits every vertex of GG exactly once before returning to vv.

The Claim

Theorem 1. Let NN be a finite simple cubic network. For every perfect matching P⊆EP\subseteq E, the complementary graph satisfies (5). deg⁡GN|E\P(v)=2(v∈V).\deg_{G_{N|_{E\setminus P}}}(v)=2 \qquad (v\in V).(5)✦ Assume in addition that NN is three-edge-connected, that B⊆VB\subseteq V gives a bipartition of NN, and that NN has a cycle cut duality with DD. For every prescribed edge e∈Ee\in E, the assertion (6) holds. ∃P⊆E:e∈P,|st⁡N(v)∩P|=1(v∈V),GN|E\P is connected.\exists P\subseteq E:\quad e\in P,\qquad \bigl|\operatorname{st}_N(v)\cap P\bigr|=1\ (v\in V),\qquad G_{N|_{E\setminus P}}\text{ is connected}.(6)✦ Under these additional hypotheses, (7) holds as well. GN has a Hamiltonian cycle.G_N\text{ has a Hamiltonian cycle}.(7)✦

In the paper, the result reads: every finite simple cubic bipartite planar 33-vertex-connected graph GNG_N has, for each edge ee, a Hamiltonian cycle avoiding ee.

What Is Checked

The matching statement (5) is stated over finite simple cubic networks; (6) and (7) additionally require three-edge connectivity, a bipartition, and a cycle cut duality. The boundary and gradient operators in (3) are real linear maps.