In the 1960s, mathematicians William Tutte and Crispin Nash-Williams separately developed theories about structures called edge-disjoint spanning trees, which now serve as one of the key technical tools in many problems about edge connectivity.
New approach to vertex connectivity could maximize networks’ bandwidth - MIT News Office Saturday, February 22, 2014 @ 4:08pm
A spanning tree is a subgraph — or a graph-within-a-graph — in which all of the nodes are connected by the smallest number of edges. A set of spanning trees within a graph are called “edge-disjoint” if they do not share any of these connecting lines.
If a network contains three edge-disjoint spanning trees, for example, information can flow in parallel along each of these trees at the same time, meaning three times more bandwidth than would be possible in a graph containing just one tree. The higher the number of edge-disjoint spanning trees, the larger the information flow, Ghaffari says. “The results of Tutte and Nash-Williams show that each graph contains almost as many spanning trees as its edge connectivity,” he says.
