The independent spanning trees conjecture

About 13 years old · traced to 2013

Let $G$ be a graph and let $v$ be any specified vertex of $G$ . A collection of spanning trees of $G$ is independent spanning trees rooted at $v$ if, for every vertex $u$ , the paths from $v$ to $u$ in the trees are pairwise internally vertex-disjoint. A graph is $k$ -connected if deleting fewer than $k$ vertices leaves it connected. Independent spanning trees conjecture. For any $k \geq 2$ , every $k$ -connected graph has $k$ independent spanning trees rooted at any vertex. The conjecture is a foundational strengthening of connectivity via spanning-tree packings. It is known for $k \leq 4$ and for planar graphs, but remains open for general $k \geq 5$ .

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

The Independent Spanning Trees Conjecture
Let $G$ be a graph, let $\kappa(G)$ denote its vertex-connectivity, and let $r\in V(G)$ be a prescribed root. Spanning trees rooted at $r$ are independent spanning trees (ISTs) if, for every vertex $v\in V(G)$ , their unique $r$ – $v$ paths are internally vertex-disjoint.

Zehavi–Itai's Independent Spanning Trees Conjecture. Every graph $G$ contains $\kappa(G)$ many ISTs rooted at $r$ , for every choice of $r\in V(G)$ .

The conjecture is a qualitative strengthening of Menger's theorem. It is known for connectivity $k=2,3,4$ , as well as for several particular graph classes, but remains open for general graphs.
source: Nemanja Draganić, Keith Frankston, Michael Krivelevich, Alexey Pokrovskiy and Liana Yepremyan, “On Independent Spanning Trees in Random and Pseudorandom Graphs”, arXiv:2509.26401 (2025).

References

Primary source

Toru Hasunuma, “Completely Independent Spanning Trees in Line Graphs”, arXiv:2209.09565 (2022).

Additional references

2 papers in this index state this conjecture (2013–2022). The statement above is taken from the most recent of them; the others are arXiv:1311.0750.

Posted 1 month ago

The independent spanning trees conjecture

The Independent Spanning Trees Conjecture

Primary source

Additional references

Progress summary

Solutions 0