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].

References

  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.
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Tutte%27s_disjoint_tree_theorem&oldid=546"