Prim's and Kruskal's Algorithms Produce Minimum Spanning Tree

Theorem

Both Kruskal's Algorithm and Prim's Algorithm always produce a minimum spanning tree.

Proof

Suppose that either algorithm produces a tree $T$.

Let there exist another spanning tree $S$ with a smaller total weight.

Let $e$ be an edge of smallest weight which lies in $T$ but not $S$.

If we add $e$ to $S$, we obtain a cycle, from Equivalent Definitions for Tree.

This cycle contains an edge $e'$ which is in $S$ but not $T$, otherwise $T$ would not be a tree.

So, we replace $e'$ in $S$ with $e$ from $T$, and obtain a new spanning tree $S'$.

From the method of construction of $T$, it follows that the weight of $e$ can not exceed that of $e'$.

So the total weight of $S'$ does not exceed the total weight of $T$.

Also, $S'$ has one more edge in common with $T$ than $S$ has.

We repeat the above procedure, and repeatedly change edges of $S$ for edges of $T$, and each time the weight of the intermediate graph does not exceed that of $T$.

Thus the weight of $T$ does not exceed that of $S$, contradicting the definition of $S$.

Hence $T$ must be a minimum spanning tree.

$\blacksquare$

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 4.1$: Theorem $4.3$