 |
 |
6 of 18 |  |
 |
 |
MIT
Tree Packing
l
Theorem
[NW]: a graph with minimum
cut c has a packing of c/2
disjoint
spanning trees.
l
Corollary: in such a packing, some tree
only crosses min-cut twice.
l
To find min-cut:
»
find a packing
»
find smallest cut a tree crosses twice.