Minimum Spanning Trees

Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vectices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.

One example would be a cable TV company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost.

Possible multiplicity

There may be several minimum spanning trees of the same weight; in particular, if all weights are the same, every spanning tree is minimum.

Uniqueness

If each edge has a distinct weight then there will only be one, unique minimum spanning tree. This can be proved by induction or contradiction. This is true in many realistic situations, such as the cable TV company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.

A proof of uniqueness by contradiction is as follows. Say we have an algorithm that finds an MST (which we will call A) based on the structure of the graph and the order of the edges when ordered by weight. (Such algorithms do exist, see below.) Assume for the moment that this MST is not unique and that there is another spanning tree, B, with equal weight. If there are n vertices in the graph, then each tree has n-1 edges. There are some edges which belong to B but not to A. What happens if we decrease the weight of one of these edges by a tiny amount ε so that we do not change the overall ordering of all the edges of the graph when ordered by weight? (This is possible because all weights are separated by positive amounts.) It will not change the result of our algorithm, which still gives tree A. But tree B will now have a weight ε less than what it had before, which means that A is not minimal, contrary to assumption. Because of this contradiction, we conclude that the assumption that there can be a second MST was false.

Minimum-cost subgraph

If the weights are non-negative, then a minimum spanning tree is in fact the minimum-cost subgraph connecting all vertices, since subgraphs containing cycles necessarily have more total weight.

Cycle property

For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of other edges of C, then this edge cannot belong to an MST. Assuming the contrary, i.e. that e belongs to an MST T1, then deleting e will break T1 into two subtrees with the two ends of e in different subtrees. The remainder of C reconnects the subtrees, hence there is an edge f of C with ends in different subtrees, i.e., it reconnects the subtrees into a tree T2 with weight less than that of T1, because the weight of f is less than the weight of e.

Cut property

For any cut C in the graph, if the weight of an edge e of C is smaller than the weights of other edges of C, then this edge belongs to all MSTs of the graph. Indeed, assume the contrary, i.e., e does not belong to an MST T₁. Then adding e to T₁ will produce a cycle, which must have another edge e₂ from T₁ in the cut C. Replacing e₂ with e would produce a tree T₁ of smaller weight.