# Deterministic construction of strong thin spanning trees

> Every k-connected network has a spanning tree that uses at most a fixed multiple of 1/k of every cut. Plain-English explainer, Lean status and sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-174/
Last updated: 2026-10-14

**Every k-connected network has a spanning tree that uses at most a fixed multiple of 1/k of every cut.**

**Trust:** Formal proof listed · **Papers:** 2 · **First paper:** September 23, 2026 · **Field:** Combinatorics · **Entry:** 174

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

A spanning tree connects all points of a network with as few links as possible. The strong thin tree conjecture says that a highly connected network has one using only a small share of every cut. This paper proves that share can be C/k for one fixed C. A companion paper gives a polynomial-time method to find the tree.

## At a glance

- **First step:** 2004 (Luis Goddyn, Problem 4 of his open problem list)
- **Significance:** Major. It settles the strong thin tree conjecture, a central question linking graph structure to route-planning algorithms.
- **Trust:** Formal proof listed
- **Field:** Combinatorics (2 papers)

## The explanation

Take two points joined by five parallel links. To connect them you need just one link. That one link is 1/5 of the links between the two points. Now use k parallel links instead of five. The single connecting link is then 1/k of them, and you can't do better[1].

That is the idea of a thin tree. A tree is a set of links that connects every point with no loops. A tree that reaches every point is a spanning tree, and it uses one fewer link than there are points[2]. A cut splits the points into two sides. The links crossing between the sides form the cut. A spanning tree is thin when it uses only a small fraction of every cut, all at once.

A network is k-edge-connected when every cut has at least k links. More connectivity should allow thinner trees. Small cases show why the question is subtle. The corners and edges of a cube give eight points and twelve links, with at least three links in every cut. A check of all 384 spanning trees shows something striking. Each one uses every link of some cut. So at this low connectivity, no tree is thin at all.

Luis Goddyn asked whether high connectivity alone forces thin trees, however large the network is[3,4]. The strong form of his question asks for thinness C/k, for one fixed number C[5]. The question matters for route planning. It is tied to approximation methods for the traveling salesman problem with one-way costs[6]. In 2015, Anari and Oveis Gharan came close. They found trees with thinness about (log log n)/k, up to a power, where n is the number of points[7]. That factor grows, very slowly, as networks get bigger.

This paper proves the strong conjecture[8]. Every k-edge-connected network with at least two points has a spanning tree using at most C/k of every cut. The number C is fixed, and it does not depend on the size of the network[9]. The two-point example shows the 1/k rate cannot be improved[1]. A companion paper gives a step-by-step method that finds such a tree in polynomial time[10]. That means the work grows like a fixed power of the input size. It still works when huge numbers of parallel links are written compactly as numbers[11]. Neither paper gives a value for C.

The obstacle is serving every cut at once. High connectivity gives many spanning trees that share no links. For any one cut, these trees use few of its links on average. But averaging does not pick out one tree that is small on every cut[12]. The proof keeps a large family of separate trees while it thins the network over and over. Each round cuts the cut sizes and the number of trees by almost the same factor[13]. The losses stay bounded across all rounds, until a single thin tree remains.

The traveling salesman link has a twist. Constant-factor approximation for that one-way problem was already found by other methods[14]. So this result settles the tree question itself, not that application.

How sure is this? A computer proof checker called Lean has checked formal versions of both results. One states that such a tree exists for one fixed C. The other states that a deterministic polynomial-time method finds it. Neither formal statement gives a numerical value for C. No specialist review of the papers has been published.

**What it doesn't show.** This does not give a numerical value for the constant C.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Major if the proofs hold. Lean has checked formal versions of the existence result and the polynomial-time construction. C has no stated value, and no specialist review is published.

## Words used

- **Spanning tree:** A set of links that connects every point of a network with no loops.
- **Cut:** The links crossing between two sides of a split of the points.
- **k-edge-connected:** Every cut has at least k links.
- **Thin tree:** A spanning tree that uses only a small fraction of the links in every cut.
- **Polynomial time:** A running time that grows like a fixed power of the input size.
- **Lean:** A computer program that checks each step of a formally written proof.

## The original papers (2)

- [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf) - September 23, 2026 · Formal proof listed
- [A polynomial-time construction of strong thin trees](https://github.com/openai/math/blob/main/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/paper.pdf) - September 23, 2026

- [Lean notes](https://github.com/openai/math/blob/main/lean/docs/174.md)

## Quoted lines from the paper (14)

[1] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> The order \(1/k\) is necessary: with two vertices and \(k\) parallel edges, every spanning tree uses exactly one of the \(k\) edges of the only cut.

[2] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> A spanning tree retains connectivity using only \(|V|-1\) edges.

[3] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> Thinness asks that these edges occupy a small fraction of every cut simultaneously. The question is whether high edge connectivity alone forces such a tree, with a bound independent of the number of vertices.

[4] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> Goddyn's thin tree conjecture asks whether, for every \(\varepsilon>0\), a sufficiently high edge connectivity guarantees an \(\varepsilon\)-thin spanning tree.

[5] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> The strong thin tree conjecture asks for the quantitative rate \(C/k\).

[6] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> Thin trees connect this graph-theoretic question with approximation algorithms.

[7] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> They proved the existence of a spanning tree with thinness \(\operatorname{poly}(\log\log n)/k\).

[8] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> Theorem … resolves this stronger conjecture positively.

[9] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> Theorem … controls all cuts simultaneously and removes the dependence on \(n\).

[10] From [A polynomial-time construction of strong thin trees](https://github.com/openai/math/blob/main/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/paper.pdf):

> A thin spanning tree must also use a small fraction of every cut, with the same tree serving all cuts simultaneously. We give a deterministic polynomial-bit construction at the inverse-connectivity scale.

[11] From [A polynomial-time construction of strong thin trees](https://github.com/openai/math/blob/main/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/paper.pdf):

> In the second representation, the number of edge copies may be exponential in the input length.

[12] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> For any fixed cut, the average number of edges used by the trees in such a packing is small. This averaging does not select one tree that is small on every cut.

[13] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> We maintain a large packing throughout a sequence of sparsifications: each step reduces cut sizes and the packing size by almost the same factor, and the accumulated relative loss remains bounded.

[14] From [The strong thin tree conjecture](https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf):

> The thin-tree approach to asymmetric traveling salesman remains structurally useful, although constant-factor approximation for that problem has already been obtained by other methods. Svensson, Tarnawski, and V\'egh proved the first such guarantee; Traub and Vygen subsequently improved it.

## Other sources

- [L. A. Goddyn, “Some Open Problems I Like”, online problem list, Problem 4 (2004), archived copy](https://web.archive.org/web/20211025204852/https://www.sfu.ca/~goddyn/Problems/problems.html)
- [A. Asadpour, M. X. Goemans, A. Mądry, S. Oveis Gharan and A. Saberi, “An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem”, Operations Research 65(4) (2017), 1043–1061](https://doi.org/10.1287/opre.2017.1603)
- [N. Anari and S. Oveis Gharan, “Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP”, FOCS 2015, 20–39](https://arxiv.org/abs/1411.4613v4)
- [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [The second Kahn–Kalai conjecture with an edge-count bound](https://closedform.nishachay.tech/e/openai-math-2026-176/) - Combinatorics
- [Seymour’s second-neighborhood conjecture](https://closedform.nishachay.tech/e/openai-math-2026-173/) - Combinatorics
- [Talagrand’s expectation thresholds, discrete convexity, and graph decompositions](https://closedform.nishachay.tech/e/openai-math-2026-175/) - Combinatorics
- [Classification of finite Euclidean Ramsey configurations](https://closedform.nishachay.tech/e/openai-math-2026-172/) - Combinatorics
- [The hypercube Ramsey conjecture](https://closedform.nishachay.tech/e/openai-math-2026-171/) - Combinatorics
- [Combinatorics](https://closedform.nishachay.tech/science/mathematics/combinatorics/) - Field · 37 results
- [Open since the 2000s](https://closedform.nishachay.tech/open-since/2000s/) - Era · 48 results
- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20174%5D%20)