Nash-Williams' forest cover theorem

From Egres Open
Jump to: navigation, search

Theorem (Nash-Williams [1]). The edges set of a graph G=(V,E) can be covered by k forests if and only if [math]i_G(X) \leq k(|X|-1)[/math] for every non-empty subset X of V.

References

  1. C. St. J. A. Nash-Williams, Decomposition of finite graphs into forests, Journal of the London Mathematical Society 39 (1964), page 12. DOI link.