Tutte's disjoint tree theorem

From Egres Open
Jump to: navigation, search

Theorem (Tutte)[1]. 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 [2].


  1. W.T. Tutte, On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961), 221-230. DOI link.
  2. 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.