Search

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.

2 papers September 23, 2026 Explained by AI

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.

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.

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. 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. The strong form of his question asks for thinness C/k, for one fixed number C. The question matters for route planning. It is tied to approximation methods for the traveling salesman problem with one-way costs. 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. That factor grows, very slowly, as networks get bigger.

This paper proves the strong conjecture. 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. The two-point example shows the 1/k rate cannot be improved. A companion paper gives a step-by-step method that finds such a tree in polynomial time. 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. 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. 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. 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. 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)

Lean notes

All quoted lines (14)
  1. The order 1/k1/k is necessary: with two vertices and kk parallel edges, every spanning tree uses exactly one of the kk edges of the only cut.
    The strong thin tree conjecture Back to text
  2. A spanning tree retains connectivity using only ∣V∣−1|V|-1 edges.
    The strong thin tree conjecture Back to text
  3. 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.
    The strong thin tree conjecture Back to text
  4. Goddyn's thin tree conjecture asks whether, for every ε>0\varepsilon>0, a sufficiently high edge connectivity guarantees an ε\varepsilon-thin spanning tree.
    The strong thin tree conjecture Back to text
  5. The strong thin tree conjecture asks for the quantitative rate C/kC/k.
    The strong thin tree conjecture Back to text
  6. Thin trees connect this graph-theoretic question with approximation algorithms.
    The strong thin tree conjecture Back to text
  7. They proved the existence of a spanning tree with thinness poly⁡(log⁡log⁡n)/k\operatorname{poly}(\log\log n)/k.
    The strong thin tree conjecture Back to text
  8. Theorem … resolves this stronger conjecture positively.
    The strong thin tree conjecture Back to text
  9. Theorem … controls all cuts simultaneously and removes the dependence on nn.
    The strong thin tree conjecture Back to text
  10. 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.
    A polynomial-time construction of strong thin trees Back to text
  11. In the second representation, the number of edge copies may be exponential in the input length.
    A polynomial-time construction of strong thin trees Back to text
  12. 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.
    The strong thin tree conjecture Back to text
  13. 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.
    The strong thin tree conjecture Back to text
  14. 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.
    The strong thin tree conjecture Back to text

Other sources

  1. L. A. Goddyn, “Some Open Problems I Like”, online problem list, Problem 4 (2004), archived copy
  2. 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
  3. N. Anari and S. Oveis Gharan, “Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP”, FOCS 2015, 20–39
  4. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Combinatorics Open since the 2000sLean-checked results