# Edmonds' disjoint arborescences theorem

From Egres Open

**Theorem (Edmonds) ^{[1]}** Let

*D=(V,A)*be a digraph with a designated root node

*r*.

*D*contains

*k*edge-disjoint spanning arborescences rooted at

*r*if and only if [math]\varrho(X)\geq k[/math] for each nonempty [math]X\subseteq V-r[/math].

The following stronger version also holds:

**Theorem (Edmonds) ^{[2]}** Let

*D=(V,A)*be a digraph with arborescences [math]F_1,\ldots,F_k[/math] rooted at

*r*. Then there exist

*k*edge-disjoint spanning arborescences [math]H_1,\ldots,H_k[/math] rooted at

*r*with [math]F_i\subseteq H_i[/math] if and only if each nonempty subset

*X*of

*V*is entered by at least as many arc as there exist

*i*with [math]F_i[/math] disjoint from

*X*.

## References

- ↑ J. Edmonds,
*Submodular functions, matroids, and certain polyhedra*, Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications (R. Guy, H. Hanani, N. Sauer and J. Schoenheim, eds., Gordon and Breach, New York, 1970), pp. 69--87; also in: Combinatorial Optimization—Eureka, You Shrink! (M. Juenger, G. Reinelt, and G. Rinaldi, eds., Lecture Notes in Computer Science 2570, Springer, Berlin, 2003), pp. 11--26. DOI link - ↑ J. Edmonds,
*Edge-disjoint branchings*. In: B. Rustin, Editor, Combinatorial Algorithms, Academic Press, New York (1973), pp. 91--96.