Deterministic construction of strong thin spanning trees. 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.
released 2026-09-23 | 6 theorems · 32 lemmas · 41 proofs · 23,146 words |
PLAY LEVEL 1 »(pdf)
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.
released 2026-09-23 | 3 theorems · 10 lemmas · 15 proofs · 17,166 words |
PLAY LEVEL 2 »(pdf)
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.