Minimum Spanning Trees

A minimum spanning tree (MST) is the lightest set of edges in a graph possible such that all the vertices are connected. Because it is a tree, it must be connected and acyclic. And it is called "spanning" since all vertices are included.

In this chapter, we will look at two algorithms that will help us find a MST from a graph.

Before we do that, let's introduce ourselves to the Cut Property, which is a tool that is useful for finding MSTs.

Cut Property

We can define a cut as an assignment of a graph’s nodes to two non-empty sets (i.e. we assign every node to either set number one or set number two).

We can define a crossing edge as an edge which connects a node from one set to a node from the other set.

With these two definitions, we can understand the Cut Property; given any cut, the minimum weight crossing edge is in the MST.

The proof for the cut property is as follows: Suppose (for the sake of contradiction) that the minimum crossing edge e were not in the MST. Since it is not a part of the MST, if we add that edge, a cycle will be created. Because there is a cycle, this implies that some other edge f must also be a crossing edge (for a cycle, if e crosses from one set to another, there must be another edge that crosses back over to the first set). Thus, we can remove f and keep e, and this will give us a lower weight spanning tree. But this is a contradiction because we supposedly started with a MST, but now we have a collection of edges which is a spanning tree but that weighs less, thus the original MST was not actually minimal. As a result, the cut property must hold.

Here is a diagram illustrating some of the arguments of the above proof: