Theorem (Tutte). An undirected graph G=(V,E) contains k edge-disjoint spanning trees if and only if
if it is k-partition-connected.
This can be regarded as a special case of the Matroid union theorem. Sometimes it is referred to as the Tutte-Nash-Williams theorem because it also appears in the paper of Nash-Williams .
- ↑ W.T. Tutte, On the problem of decomposing a graph into n connected factors,
J. London Math. Soc. 36 (1961), 221-230. DOI link.
- ↑ C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, The Journal of the London Mathematical Society 36 (1961), 445–450. DOI link.