Thin Tree Conjecture: How OpenAI’s Proof Controls Every Cut at Once

In a complete graph on four vertices, a star is a perfectly good spanning tree. Yet it uses all three edges that leave its center. The thin tree conjecture asks how sparse a single spanning tree can be across every cut when the original graph is highly connected. In a September 23, 2026 preprint, OpenAI proves that a deterministic polynomial-time algorithm can find a tree that uses at most $C/k$ of the edges across each cut of any finite $k$-edge-connected loopless multigraph, for a universal constant $C$. The guarantee applies to the same output tree across all cuts, even when the input stores parallel-edge counts in binary.

1. What Is the Thin Tree Conjecture? Understanding the All-Cut Condition

A spanning tree connects all $n$ vertices without cycles and uses $n-1$ edges. For a nonempty proper vertex set $S$, the cut $\delta_G(S)$ contains every edge with one endpoint in $S$ and the other outside it. Each parallel copy counts separately. A graph is $k$-edge-connected if every such cut contains at least $k$ edges. A spanning tree $T$ is $\alpha$-thin if $|\delta_T(S)|\leq\alpha|\delta_G(S)|$ for every nontrivial $S$.

In the four-vertex example, isolate vertex A. The star retains all three edges across that cut, while the path retains just one. Change the cut to the alternating vertices A and C, and all three path edges cross, out of four graph edges. The same path therefore has ratios of $1/3$ and $3/4$ on these two cuts. The objective measures the worst ratio over every choice of vertex set.

2. The Strong Thin Tree Conjecture and the Inverse-Connectivity Bound

Goddyn’s qualitative conjecture asks whether, for each positive thinness target, sufficiently large edge connectivity guarantees a tree meeting that target, with a threshold independent of the vertex count. The strong thin tree conjecture specifies the rate. A single absolute constant should suffice for all graphs, with the guaranteed fraction shrinking in inverse proportion to $k$.

Take two vertices joined by $k$ parallel edges. There is one cut up to exchanging its sides. All $k$ copies cross it, and every spanning tree selects exactly one copy. Its cut ratio is exactly $1/k$. As $k$ grows, this family rules out a universal bound of smaller asymptotic order. It also shows why parallel edges belong in the theorem: the connectivity can grow while the vertex count stays fixed. The lower bound establishes the rate, leaving the best universal constant as a separate question.

3. Earlier Thin-Tree Bounds and Their Scope

The maximum-entropy spanning-tree rounding of Asadpour and colleagues gave the constructive thinness scale $O(\log n/(k\log\log n))$. The extra factor depends on the number of vertices. Anari and Oveis Gharan improved the existence bound to $\operatorname{poly}(\log\log n)/k$ for general multigraphs and developed the effective-resistance and hierarchy methods that the new work extends. Their bound still depends on $n$ and comes from an existence proof.

For planar graphs and graphs on a fixed orientable surface, Oveis Gharan and Saberi had already obtained constructive inverse-connectivity bounds. Other results focus on the cuts themselves. Klein and Olver handle a prescribed laminar family, where any two sets are nested or disjoint. Klein, Olver, and Yeoh construct a tree that crosses each cut smaller than $(1+1/40)k$ at most 88 times. The new result removes the dependence on graph order in the general all-cut setting and gives a deterministic construction.

4. OpenAI’s Polynomial-Time Theorem

Theorem 1.1 takes a finite, undirected, loopless multigraph $G$ on at least one vertex and a positive integer $k$ for which $G$ is $k$-edge-connected. There is a universal constant $C$ such that the deterministic algorithm returns a spanning tree $T$ satisfying

The input may list labeled edge copies explicitly or give endpoint pairs with binary-encoded nonnegative integer multiplicities. The running time is polynomial in the total binary input length in either representation. On one vertex the algorithm returns the empty tree, and the cut condition is vacuous. The companion preprint proves existence and supplies the hierarchy geometry. The algorithmic paper turns that approach into a finite search with rational arithmetic and controlled precision. Both preprints appear in OpenAI’s October mathematics release.

5. Why Spanning Tree Packing Alone Falls Short

The Nash–Williams–Tutte theorem characterizes when a graph $H$ has $q$ edge-disjoint spanning trees. For each partition $\mathcal P$ of the vertices, the number of edges joining distinct parts must be at least $q(|\mathcal P|-1)$. Each tree needs at least $|\mathcal P|-1$ such edges to join the parts, and the theorem makes the condition sufficient. Summing the connectivity bounds on all parts counts each crossing edge twice. This gives at least $\lfloor k/2\rfloor$ disjoint trees for a $k$-edge-connected graph, with one tree available by connectedness when $k=1$.

For a fixed cut, disjointness caps the average tree load at the graph’s cut size divided by the number of trees. The tree below that average can depend on the cut. The construction instead selects a subgraph that reduces every cut load while retaining a large packing.

6. Metric-Cone Shortcuts and Effective Resistance

Work in the subspace perpendicular to the all-ones vector. For an oriented edge $e=uv$, let $b_e$ be the difference between the coordinate unit vectors at its endpoints. The graph Laplacian $L_H$ sums the outer products of these incidence vectors. A shortcut matrix $X$ is positive definite on that subspace and assigns each edge a resistance $R_e(X)=b_e^\top X^{-1}b_e$. With the Laplacian in place of $X$, this is the usual effective resistance for unit edge conductances.

The algorithm uses a metric test cone of centered positive semidefinite matrices $Z$ whose squared distances $d(u,v)=b_{uv}^\top Zb_{uv}$ obey the triangle inequality. A centered cut indicator gives a rank-one member of this cone. In the feasible set for $X$, the trace pairing against every such test is bounded above by three times the pairing with $L_H$. In particular, evaluating $X$ on a centered cut indicator gives at most three times the cut size.

The hierarchy proof uses a second geometry for the same vertex labels. It doubles the metric space, placing each point opposite a partner so their distances from any profile point sum to a common constant. In the convex hull of distance profiles, radii are affine. Moving toward a center or its partner changes the radius by exactly the distance traveled. This lets the proof trim balls into shells and charge their widths to lengths of graph edges crossing them. The charging bounds control average resistance on marked hierarchy boundaries, providing a simultaneous geometric response to nested partitions.

7. Convex Capacity Ramps and Low-Resistance Tree Packing

A hard resistance threshold can discard many edges at once and destroy a packing. Section 3 assigns continuous capacities instead. At a positive parameter $s$, an edge gets full ramp capacity when $sR_e(X)\leq1/2$, zero when $sR_e(X)\geq1$, and a continuously varying capacity in between. A small positive baseline keeps capacities available for the partition argument. The algorithm raises $s$ gradually while updating $X$ and lowering the target packing size by a controlled amount.

Partition inequalities require sufficient total capacity between the parts of every partition. Uncrossing reduces a hypothetical obstruction to a chain of nested partitions, where the geometric response works simultaneously. Exact rational separation checks the constraints without listing every partition. The oracle trades the partition test for inequalities involving minimum spanning tree lengths.

A minimum spanning tree computation can then expose a violated tree constraint in the rational linear program used by the oracle. The proof supplies a quantitative interior ball for the ellipsoid method and a rounding margin that keeps the output rational and feasible. At the last step, dropping the baselines loses less than one unit across any partition. Graphic-matroid union then extracts actual edge-disjoint trees from the active edges. In a graphic matroid the independent edge sets are forests, and the spanning trees of a connected graph are its matroid bases.

Proposition 3.1 starts with $r$ disjoint trees in an explicitly listed multigraph on at least two vertices, for $r$ at or above an absolute threshold. It returns a rational shortcut and a packing of $q$ trees with

Here $A$ is absolute, and the resistance bound applies to every edge in the returned packing.

8. Rank-Preserving Normalization Through Sparsification

The cut representation alone gives no lower bound on how many edges survive between the parts of an arbitrary partition. Section 4 builds a second vector system from the union of the $q$ trees. It drops one row of the incidence matrix, chooses positive edge weights by approximate minimization of a log-determinant objective, then whitens the weighted columns. Whitening is a common linear change of coordinates that makes the sum of their outer products the identity.

The derivatives of the objective are weighted edge leverage scores minus $1/q$. A small gradient makes each squared vector norm at most $(1+4/r)/q$. Positive column scalings and a common invertible map preserve the rank of every subset of incidence columns. For a partition into $d$ parts, the internal edges then span at most $n-d$ dimensions. At least $d-1$ dimensions are available to test the crossing edges. This is how the frame turns a lower bound on retained covariance into a lower bound on the number of retained edges across each partition.

9. Certified Matrix Signing Selects the Edges

For each edge in the packing, the algorithm stacks the shortcut vector $X^{-1/2}b_e$ above the rank-preserving vector $z_e$. The shortcut bounds the squared norm of the first block, and normalization bounds the second. One signing therefore acts on both representations of the same edge. The positive signs identify the edges to keep. A signing bounds the deviation of the selected outer-product sum from half the original sum. Because the two representations share one sign per edge, the algorithm produces a single subgraph that satisfies both matrix estimates.

The stack can contain irrational entries, so Section 5 approximates scaled copies of the columns by rational vectors. It decomposes the positive semidefinite residual into rational outer products and adds padding to complete the covariance exactly to the identity. Extra coordinates let the proof control the effect of discarding the padding after signing. Appendix A gives a finite-bit implementation of the rank-one signing method of Ezeunala and Jiang. An exact rational positive semidefinite test certifies the selected set, with a proved allowance for approximation error. The resulting covariance is within $C_s r^{-1/8}$ of half the original stacked covariance in operator norm, for an absolute constant $C_s$.

10. Repeated Sparsification Produces One Thin Tree

Lemma 6.1 uses the two diagonal blocks of the certificate differently. The upper bound on the shortcut block limits the load on each cut to a fraction $a_r=1/2+3C_s r^{-1/8}$ of its previous size. The lower bound on the normalized frame, projected onto the directions left by the internal edges of each partition, certifies a surviving packing of size $r^{\prime}$. It lies between $r/4$ and $r/2$ and is close enough to half that

Here $C_1$ is absolute. Multiplying the bounds over the rounds telescopes the packing ratios to the final packing size divided by the initial one. The extra factors also have a bounded product. Read the packing sizes backwards: each earlier size is at least twice the next. The sum of their inverse sixteenth powers is bounded by a geometric series, and the logarithm of the product is bounded by a constant times that sum.

The initial packing has size at least $k/3$. The algorithm stops once the packing size is below a fixed absolute threshold and still at least one. Any spanning tree of the final connected graph inherits its cut upper bounds. This yields the inverse-connectivity guarantee without a graph-size factor from the number of rounds.

11. Binary Multiplicities, Cost-and-Cut Rounding, and the Result’s Limits

Expanding a binary multiplicity can take exponential space. Section 6 first caps each endpoint pair’s count at $k$. A cut still has capacity at least $k$: either one capped pair contributes $k$, or every crossing count stays the same. The algorithm multiplies the capped counts by $2n^2/k$ and rounds down. A cut crosses at most $n^2/4$ unordered pairs, so the rounding loss leaves at least $n^2$ edges on every cut. The auxiliary graph has fewer than $n^4$ explicit edges. Its cut sizes are bounded above by the original sizes times $2n^2/k$. A tree uses at most one copy per pair, so each selected pair lifts to an original edge. The auxiliary bound of $C/n^2$ becomes $2C/k$ in the original graph, with the factor two absorbed into the universal constant.

Corollary 7.1 takes a finite undirected graph on at least two vertices with explicitly listed edge records, allowing loops and parallel records. Nonnegative rational masses $x_e$ and costs $c_e$ are given in binary, with total mass $x(\delta_G(S))\geq1$ on every nontrivial cut. Fix an integer $B\geq\max\{1,C\}$. In polynomial bit time it finds a spanning tree in the positive support, with total tree cost $c(T)$, satisfying both

The cut bound holds for every nontrivial $S$. The proof compresses fractional masses into integer multiplicities and, for large enough instances, repeatedly extracts and deletes thin trees. Selecting the cheapest uses disjointness to bound cost by the average, with the cut estimates already guaranteed. Costs need no metric assumption. When several parallel records share endpoints, the proof combines their fractional masses and uses the cheapest positive-mass record when lifting the selected tree. This preserves the fractional mass on every cut before rounding and can only lower the fractional cost charged to that endpoint pair. This thin-and-cheap rounding is relevant to asymmetric traveling salesman relaxations. Constant-factor ATSP algorithms already existed, and the paper gives no new approximation ratio for that problem or implementation benchmarks for thin-tree construction.

The thin tree conjecture thus has an algorithmic resolution whose defining feature is the coupling of cut control with packing preservation. Follow Binary Verse AI for more research explainers on graph algorithms, including maximum-cardinality matching, graph coloring, and graph isomorphism tests. For this result, OpenAI’s Lean scope covers the existence bound and the deterministic polynomial-time guarantee for explicit and binary-multiplicity inputs. The Lean proof module is separate from the comparator statement. The scope document describes these guarantees at the theorem level.

12. Frequently Asked Questions