11.19 Correctness Proofs

Minimum spanning tree algorithms are short.

algorithmsgraphsspanning-trees

11.19 Correctness Proofs

Problem

Minimum spanning tree algorithms are short. Their correctness proofs are not optional.

Kruskal, Prim, and Borůvka all make greedy choices. A greedy algorithm is risky unless each local decision can be shown to preserve a globally optimal solution. Without a proof, the algorithm may look plausible while silently failing on edge cases.

The goal of this section is to give reusable proof templates for MST algorithms.

Solution

Most MST correctness proofs use three tools:

  1. The cut property.
  2. The cycle property.
  3. An exchange argument.

Once you know which tool applies, the proof becomes mechanical.

Use the cut property when an algorithm adds an edge.

Use the cycle property when an algorithm rejects or removes an edge.

Use an exchange argument when you need to transform one spanning tree into another without increasing cost.

Proof Template: Safe Edge

This is the most common MST proof pattern.

You have a partial solution:

A

and a candidate edge:

e

You want to show that adding e is safe.

The proof shape is:

1. Identify a cut respected by the current partial solution.
2. Show that e is the lightest edge crossing that cut.
3. Apply the cut property.
4. Conclude that e belongs to some MST extending the current partial solution.

This is the proof behind Kruskal, Prim, and Borůvka.

Cut-Property Proof

Let a cut divide the graph into:

S
V - S

Let e be the minimum-weight edge crossing the cut.

Take any MST T.

If T already contains e, we are done.

If not, add e to T. This creates one cycle.

That cycle crosses the cut. Therefore it contains another crossing edge f.

Since e is minimum among crossing edges:

w(e) <= w(f)

Remove f.

The result is still a spanning tree, and its total weight is no larger than before.

Therefore there exists an MST containing e.

Proof Template: Rejecting an Edge

This pattern appears in Kruskal.

Suppose the algorithm considers an edge:

e = (u, v)

but u and v are already connected in the current forest.

Adding e creates a cycle.

If edges are processed in nondecreasing order, then every edge already on that path has weight less than or equal to w(e).

Therefore e is a maximum-weight edge on that cycle.

By the cycle property, rejecting it cannot remove the possibility of building an MST.

Cycle-Property Proof

Let C be a cycle.

Let e be strictly heavier than every other edge in C.

Assume, for contradiction, that some MST T contains e.

Remove e from T. The tree splits into two components.

Because e lies on cycle C, there is another edge f in C that reconnects those two components.

Since:

w(f) < w(e)

replacing e with f gives a spanning tree of smaller total weight.

That contradicts minimality.

Therefore e cannot belong to any MST.

Kruskal Correctness

Kruskal processes edges in nondecreasing order and accepts an edge only if it connects two different components.

To prove correctness:

  1. At any point, the accepted edges form a forest.
  2. When Kruskal accepts an edge, it connects two components.
  3. Those two components define a cut.
  4. Because edges are processed in sorted order, the accepted edge is the lightest available edge crossing that cut.
  5. By the cut property, the edge is safe.
  6. After V - 1 accepted edges, the forest is a spanning tree.
  7. Since every accepted edge was safe, the result is an MST.

The forest invariant matters. Kruskal never accepts an edge whose endpoints are already connected, so it never creates a cycle.

Prim Correctness

Prim maintains one growing tree.

At each step:

S = vertices already in the tree

The remaining vertices are:

V - S

This defines a cut.

Prim chooses the minimum-weight edge crossing that cut.

By the cut property, that edge is safe.

After repeating this process until every vertex is included, the selected edges form a spanning tree.

Since every selected edge was safe, the result is an MST.

Borůvka Correctness

Borůvka maintains a forest of components.

During each phase, every component selects its cheapest outgoing edge.

For a component C, the cut is:

C
V - C

The selected edge is the lightest crossing edge for that cut.

By the cut property, it is safe.

Adding all selected edges preserves optimality because each selected edge is safe for some MST extension. After repeated phases, all components merge into one tree.

Therefore the result is an MST.

Exchange Argument Pattern

Exchange arguments prove that one solution can be transformed into another.

The usual MST exchange looks like this:

1. Start with an MST T.
2. Add a candidate edge e.
3. This creates a cycle.
4. Remove another edge f from that cycle.
5. The graph remains a spanning tree.
6. Compare w(e) and w(f).
7. Show the new tree is no more expensive.

This pattern appears so often that it is worth memorizing.

Invariants

A good MST proof usually names an invariant.

For Kruskal:

The accepted edges form a forest that can be extended to some MST.

For Prim:

The selected edges form a tree that can be extended to some MST.

For Borůvka:

The selected edges form a forest that can be extended to some MST.

The invariant is what lets the proof survive multiple greedy choices.

Handling Equal Weights

Equal weights do not break MST algorithms.

They do affect proof wording.

When using the cut property, use:

w(e) <= w(f)

not:

w(e) < w(f)

This proves that the exchanged tree is no more expensive.

When using the cycle property to prove that an edge never appears in an MST, strict inequality is required:

w(e) > w(f)

for every other edge in the cycle.

If weights are equal, the edge may appear in some MST.

Disconnected Graphs

If the graph is disconnected, no spanning tree exists.

Kruskal and Borůvka naturally produce a minimum spanning forest.

Prim started from one vertex only covers that vertex's connected component unless repeated from each unvisited vertex.

A correctness proof must state whether the input graph is assumed connected.

If the graph is not connected, the correct object is a forest, not a tree.

Minimality Versus Connectivity

A common proof error is to show only that the algorithm produces a spanning tree.

That proves feasibility, not optimality.

You need both parts:

Requirement Meaning
Spanning tree The output is connected and acyclic
Minimum No other spanning tree has smaller total weight

The cut property and exchange argument establish minimality.

Example Proof: Kruskal

Here is the compact proof form.

Kruskal accepts edges in sorted order only when they join different components. Therefore the accepted edges are always acyclic. When an edge e is accepted, it crosses the cut formed by one of the current components and the rest of the graph. No lighter edge crossing that cut remains unprocessed, and any lighter processed edge that crossed the cut would already have merged the components. Thus e is a lightest crossing edge. By the cut property, e is safe. Repeating this argument for each accepted edge shows that the final forest can be extended to an MST. When the graph is connected and V - 1 edges have been accepted, the forest is a spanning tree, so it is an MST.

Example Proof: Prim

Prim maintains a set S of vertices in the current tree. At each step it selects the lightest edge crossing from S to V - S. This edge is safe by the cut property. Adding it preserves the tree structure because it introduces exactly one new vertex. After V - 1 steps, every vertex has been added, so the selected edges form a spanning tree. Since each selected edge was safe, the spanning tree has minimum total weight.

Example Proof: Borůvka

During a Borůvka phase, each component selects its lightest outgoing edge. For any component C, this edge is the lightest edge crossing the cut (C, V - C), so it is safe by the cut property. Adding the selected edges merges components without increasing the minimum possible cost. Repeating phases eventually leaves one component if the graph is connected. The selected edges form a spanning tree, and every selection was safe, so the result is an MST.

Common Mistakes

Proving Only That the Output Is Connected

Connectivity does not imply minimum cost.

Forgetting the Acyclic Condition

A connected graph with extra edges is not a spanning tree.

Using the Cycle Property with Equal Weights

Strict inequality is required to exclude an edge from all MSTs.

Not Stating the Input Assumption

Connected graph gives MST. Disconnected graph gives minimum spanning forest.

Treating Greedy Choice as Obvious

Every greedy choice needs a safe-edge argument.

Recipe

When writing an MST correctness proof:

  1. State the input assumptions.
  2. State the algorithm invariant.
  3. Prove accepted edges remain acyclic.
  4. Identify the relevant cut or cycle.
  5. Apply the cut property for chosen edges.
  6. Apply the cycle property for rejected edges.
  7. Use an exchange argument when needed.
  8. Show the algorithm terminates with exactly V - 1 edges.
  9. Conclude that the output is a minimum spanning tree.

Correctness proofs for MST algorithms are compact once the right template is in place. The main discipline is to separate feasibility from optimality: first show that the output is a spanning tree, then show that every greedy choice preserves minimum possible cost.