OP-00726 Solution claimed

Strong thin-tree conjecture

Let $G = (V, E)$ be a finite undirected loopless multigraph with at least two vertices, parallel edges counted separately. For a nonempty proper subset $S \subsetneq V$ write $\delta_G(S)$ for the set of edges with exactly one endpoint in $S$. For an integer $k \ge 1$, $G$ is $k$-edge-connected if $|\delta_G(S)| \ge k$ for every such $S$. Goddyn's thin tree conjecture asks whether, for every $\varepsilon > 0$, sufficiently high edge connectivity forces a spanning tree $T$ with $|T \cap \delta_G(S)| \le \varepsilon |\delta_G(S)|$ for every $S$; Anari and Oveis Gharan state its strongest form, with $\varepsilon$ of order $1/k$. They proved that every $k$-edge-connected graph on $n$ vertices has a spanning tree satisfying these inequalities with $\varepsilon = \operatorname{polyloglog}(n)/k$. Klein, Olver and Yeoh constructed, in polynomial time, a spanning tree that is $O(1/k)$-thin on every cut with fewer than $(1 + 1/40)k$ edges.

Problem. Is there an absolute constant $C > 0$ such that, for every $k \ge 1$, every $k$-edge-connected $G$ has a spanning tree $T \subseteq E$ with $$|T \cap \delta_G(S)| \le \frac{C}{k}\, |\delta_G(S)| \qquad \text{for every } \varnothing \ne S \subsetneq V?$$ The same tree must satisfy every cut inequality, $C$ must not depend on $k$, $G$ or $|V|$, and only existence is asked, not an efficient construction.

Source: Goddyn (2004), the thin tree conjecture, in its strongest form (thinness of order 1/k) as stated by Anari and Oveis Gharan (2015) after their Conjecture 1.3; stated in this form by AIM — Open Applied Problems.

Imported from github.com/MColbrook/AIM.

Classification

Primary: CO — Combinatorics
Secondary: OC
Keywords: AIM Open Applied Problems, edge connectivity, spanning trees, thin trees

References

@inproceedings{anari2015,
  author        = {Anari, Nima and Oveis Gharan, Shayan},
  title         = {Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric {TSP}},
  booktitle     = {2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)},
  publisher     = {IEEE},
  year          = {2015},
  pages         = {20--39},
  doi           = {10.1109/FOCS.2015.11},
  eprint        = {1411.4613},
  archivePrefix = {arXiv},
}
@inproceedings{klein2026,
  author    = {Klein, Nathan and Olver, Neil and Yeoh, Zi Song},
  title     = {Thin Trees for near Minimum Cuts},
  booktitle = {53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  series    = {LIPIcs},
  volume    = {374},
  year      = {2026},
  pages     = {129:1--129:18},
  doi       = {10.4230/LIPIcs.ICALP.2026.129},
}
@misc{aim-strong-thin-tree,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Strong thin-tree conjecture}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/1b7c7fd251c1643bb41f0e3cef38704bcef410fd/problems/323-strong-thin-tree.md},
  note         = {Entry 323 at commit 1b7c7fd, 2026-10-13},
}

Resolution claims

The strong thin tree conjecture v1 GitHub ↗

OpenAI

We prove that every finite loopless $k$-edge-connected multigraph on at least two vertices, with $k\ge1$, 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.

Full resolution · not verified · fidelity not established · posted on GitHub 6 Oct 2026

Status history

When	Change	By	Reason
2026-10-16	Needs verification → Solution claimed	—	Recorded here: math @ 1581d4c, source/main.tex.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00726, "Strong thin-tree conjecture", clopen.solutions.