Resolves the strong thin-tree conjecture constructively. Every finite loopless k-edge-connected multigraph on at least two vertices has a spanning tree containing at most a universal C/k fraction of the edges of every cut. Such a tree can be found deterministically in polynomial time, even with binary-encoded parallel-edge multiplicities. (Lean)
Manuscripts (2)
The strong thin tree conjecture
September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:The-strong-thin-tree-conjecture-September-23-2026}
We prove that every finite loopless k-edge-connected multigraph on at least two vertices, with k ≥ 1, has a spanning tree meeting each cut in at most C/k times the size of the cut, where C is a universal constant. This resolves the strong thin tree conjecture.
A polynomial-time construction of strong thin trees
September 23, 2026 · source · cite as \cite{OAI:A-polynomial-time-construction-of-strong-thin-trees-September-23-2026}
We give a deterministic polynomial-time construction of strong thin trees. Given a finite k-edge-connected loopless multigraph on at least one vertex, the algorithm constructs a spanning tree meeting every cut in at most a C/k fraction of its edges, for a universal constant C. The running time is polynomial in the binary input length, including when parallel-edge multiplicities are encoded in binary.
Result 174 · Combinatorics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md