Greedy: Minimum Spanning Tree Correctness

Understanding why greedy algorithms reliably find minimum spanning trees is not just an academic exercise—it’s the foundation for designing efficient networks, from power grids to communication systems. These algorithms are fast and intuitive, but their correctness hinges on two fundamental properties that guarantee the optimal solution is built one careful choice at a time. Mastering these proofs transforms you from someone who uses algorithms into someone who understands why they work, enabling you to adapt these principles to new problems.

Foundations: Spanning Trees and the Greedy Approach

A minimum spanning tree (MST) of a connected, undirected graph with weighted edges is a subgraph that includes all vertices, is a tree (acyclic and connected), and has the minimum possible total edge weight. Greedy algorithms construct an MST by making a series of locally optimal choices—always adding the cheapest available edge that doesn’t create a problem. The power of this approach lies in its simplicity and efficiency, but its validity is not obvious. Why should picking the cheapest edge at each step, without considering the global picture, always yield the globally cheapest tree? The answer is encapsulated in two structural properties of graphs: the cut property and the cycle property. These properties are the mathematical bedrock that justifies algorithms like Kruskal’s, Prim’s, and Borůvka’s.

The Cut Property: The Lightest Edge Across a Divide

The cut property states that for any cut (a partition of the graph's vertices into two non-empty sets) in a graph, the minimum-weight edge crossing that cut must be part of some minimum spanning tree. A cut is simply a division of the vertex set $V$ into two subsets $S$ and $V\setminus S$. An edge crosses the cut if one of its endpoints is in $S$ and the other is not. This property is the primary engine behind Prim’s algorithm.

To prove the cut property, consider a cut $(S,V\setminus S)$ and let $e$ be the unique lightest edge crossing it. For contradiction, assume no MST contains $e$. Take any MST $T$. Since $T$ connects all vertices, it must have at least one edge, say $f$, crossing the same cut to connect $S$ and $V\setminus S$. By our assumption, $w(e)<w(f)$. Now, add edge $e$ to $T$. This creates a single cycle that must include $f$, as $e$ now provides a second connection across the cut. Remove $f$ from this cycle. The result is a new spanning tree, $T^{\prime }=T\cup \{e\}\setminus \{f\}$. Its total weight is $w(T^{\prime })=w(T)-w(f)+w(e)<w(T)$, contradicting the minimality of $T$. Therefore, some MST must include $e$.

Think of a cut as a canyon dividing two regions. The cheapest bridge (edge) across that canyon is always part of the most economical road network (MST). Prim’s algorithm operationalizes this by starting with a single-vertex set $S$ and repeatedly using the cut property to add the cheapest edge from $S$ to the rest of the graph, thereby growing the tree one vertex at a time.

The Cycle Property: The Heaviest Edge on a Loop

Complementing the cut property is the cycle property. It states that for any cycle in the graph, the maximum-weight edge on that cycle cannot be part of any minimum spanning tree. This property is central to the correctness of Kruskal’s algorithm.

The proof uses a similar exchange argument. Let $C$ be a cycle in graph $G$, and let $e$ be the heaviest edge on $C$. Assume, for contradiction, that an MST $T$ contains $e$. Removing $e$ from $T$ splits it into two disconnected subtrees. Since $C$ is a cycle containing $e$, the path $C-e$ connects the two endpoints of $e$ through other edges. Therefore, there must be at least one other edge $f$ on $C$ that connects these two subtrees. Crucially, since $e$ is the heaviest edge on $C$, we have $w(f)\le w(e)$. Now, add $f$ to the disconnected subtrees. The result, $T^{\prime }=T\cup \{f\}\setminus \{e\}$, is a new spanning tree. Its weight is $w(T^{\prime })=w(T)-w(e)+w(f)\le w(T)$. If $w(f)<w(e)$, then $w(T^{\prime })<w(T)$, contradicting minimality. If $w(f)=w(e)$, then $T^{\prime }$ is also an MST, proving that $e$ is not uniquely necessary. In either case, there exists an MST without $e$.

Imagine a cycle as a redundant loop in a network. The most expensive link on that loop is wasteful; you can always remove it and use cheaper edges to maintain connectivity. Kruskal’s algorithm builds an MST by sorting all edges and adding them in increasing weight order, but it skips an edge if it would form a cycle with already-selected edges. The cycle property ensures that by skipping an edge that would complete a cycle, you are never discarding an edge essential for an MST, because if it were essential, it would be the heaviest on that cycle—which is impossible.

Proving Algorithm Correctness with the Properties

The cut and cycle properties are not just isolated facts; they are the lenses through which we prove the correctness of the three classic greedy MST algorithms. Each algorithm uses a different strategy to implicitly apply these properties at every step.

Kruskal’s Algorithm correctness follows directly from the cycle property. The algorithm maintains a forest (a collection of trees), initially with no edges. It considers edges in non-decreasing order of weight. For each edge $e$, if adding $e$ does not create a cycle in the current forest, it is included. The algorithm terminates when the forest becomes a single tree spanning all vertices. Why is this correct? When the algorithm considers an edge $e=(u,v)$, if $u$ and $v$ are in different trees in the current forest, adding $e$ connects them. If they are in the same tree, adding $e$ would create a cycle. Since all edges lighter than $e$ have already been considered and added if possible, any cycle formed would have $e$ as its heaviest edge. By the cycle property, $e$ cannot belong to any MST, so it is safely discarded. Thus, every added edge is justified by the cut property across the cut defined by the two trees it connects, and every discarded edge is justified by the cycle property.

Prim’s Algorithm is a direct embodiment of the cut property. It starts from an arbitrary root vertex, maintaining a tree $T$ that grows from this root. At each step, it considers the cut between the vertices in $T$ and the vertices not yet in $T$. It selects the lightest edge crossing this cut and adds it (along with its new vertex) to $T$. By the cut property, this edge must be in some MST. Since the algorithm’s choices are consistent with building a single tree, the final result is an MST. The proof is inductive: assuming the current tree $T$ is a subset of some MST, adding the lightest edge from the cut between $T$ and the remaining vertices preserves this property, leading to a complete MST.

Borůvka’s Algorithm (or Sollin’s algorithm) uses both properties in a parallel fashion. In each iteration, for every connected component (initially single vertices), it finds the cheapest edge connecting that component to another component and adds all such edges simultaneously. This is equivalent to applying the cut property to the cut defined by each component. Adding these edges may create cycles, but Borůvka’s algorithm merges components, and any cycle formed will have its heaviest edge discarded in later iterations due to the cycle property. The algorithm iterates until only one component remains. The proof of correctness relies on showing that each added edge is the lightest across some cut and that parallel additions don’t compromise optimality because any cycle created will contain a heavier edge that can be removed.

Common Pitfalls

When working with these concepts, several subtle errors frequently arise. Recognizing and avoiding them sharpens your understanding.

1. Misidentifying Cuts for the Cut Property: A common mistake is to incorrectly define a cut, such as using a set of edges instead of a partition of vertices. Remember, a cut is defined by a subset of vertices $S$. The edges crossing it are those with one endpoint in $S$ and one outside. For example, in Prim’s algorithm, the cut is between the current tree and the rest of the graph, not between arbitrary groups of edges. Always verify that your cut divides all vertices into two non-empty groups.

1. Assuming the Cut Property Guarantees Uniqueness: The cut property states the lightest edge across a cut is in some MST, not necessarily in every MST. If multiple edges have the same minimum weight across a cut, any of them could be chosen, leading to multiple possible MSTs. This is why algorithms like Prim’s still work correctly when there are ties—they pick one light edge, which is sufficient.

1. Confusing the Cycle Property with Shortest Paths: The cycle property is specific to spanning trees, not paths. It says the heaviest edge on any cycle is not in any MST. Students sometimes mistakenly apply it to shortest path problems, where different rules apply. For instance, in a cycle, the heaviest edge might still be part of the shortest path between two vertices if it bypasses even heavier alternatives. Keep the context clear: MSTs minimize total weight of a connecting tree, not path weight between two points.

1. Overlooking the Need for Distinct Weights in Proofs: The standard proofs often assume distinct edge weights for simplicity. When weights are not distinct, the arguments still hold, but you must handle equal weights carefully. For example, in the cycle property proof, if $w(f)=w(e)$, the new tree $T^{\prime }$ has equal weight, showing $e$ is not uniquely required. Algorithms handle ties arbitrarily without affecting correctness. Always consider the non-strict inequalities in your reasoning.

Summary

• The cut property guarantees that for any partition of vertices, the cheapest edge connecting the two parts must be included in some minimum spanning tree. This property directly justifies Prim’s algorithm and is used in Borůvka’s algorithm.
• The cycle property ensures that the most expensive edge on any cycle in the graph is never part of any MST. This is the foundational reason Kruskal’s algorithm can safely discard edges that would create cycles.
• Proving these properties involves exchange arguments: assuming an optimal solution without the property leads to a contradiction by constructing a spanning tree with strictly lower or equal weight.
• Kruskal’s, Prim’s, and Borůvka’s algorithms are all correct because their operational rules—adding edges in sorted order without cycles, growing a tree from a cut, and parallel component merging—are systematic applications of the cut and cycle properties.
• Understanding these proofs equips you to not only implement MST algorithms confidently but also to analyze and design new greedy strategies for other optimization problems on graphs.