Question

Prove that Kruskal’s algorithm produces minimum spanning trees.

Short answer

Kruskal's algorithm produces minimum spanning trees.

Step-by-step solution

Definition

Kruskal's algorithm:

Start from a graph \({\bf{T}}\) that contains only the vertices and no edges. Repeatedly select the edge in the given graph \({\bf{G}}\) with the smallest weight (that doesn't cause a circuit) and add it to the graph \({\bf{T}}\). Once the graph is connected, we have found a minimum spanning tree.

Given: \({\bf{G}}\) is a connected undirected weighted graph.

Proof by contradiction

To proof: Kruskal's algorithm produces a minimum spanning tree of \({\bf{G}}\)

Let \({\bf{S}}\) be the tree produced by Kruskal's algorithm and let \({{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{{\bf{n - 1}}}}\) be its edges in the order chosen (edges at the same stage are ordered arbitrarily).Let \({\bf{T}}\) be the minimum spanning tree that contains all the edges \({{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}\) (for the largest possible value of \(k\)).

\(0 \le k \le n{\bf{ - }}1\)

Let us assume that \({\bf{k < n - 1}}\). Let \(T'{\bf{ = }}T \cup \{ {{\bf{e}}_{{\bf{k + 1}}}}\} \). Since \({\bf{T}}\) is a tree, \(T'\) needs to contain a simple circuit \({\bf{C}}\) that contains

the edge \({{\bf{e}}_{{\bf{k + 1}}}}\). Then there exists another edge \(e\) in \({\bf{C}}\) that is not contained in \({\bf{S}}\) (as \({\bf{S}}\) is a tree). Moreover, this edge \(e\) was available at the stage where \({{\bf{e}}_{{\bf{k + 1}}}}\) was chosen and thus the weight of \({{\bf{e}}_{{\bf{k + 1}}}}\) has to be smaller than the weight of \(e'\)) (or come first in lexicographic order when equal weight).

\({\bf{w}}({{\bf{e}}_{{\bf{k + 1}}}}) \le w(e)\)

Minimum spanning tree

Let \(T''{\bf{ = }}T \cup \{ {{\bf{e}}_{{\bf{k + 1}}}}\} {\bf{ - }}\{ e\} \), then the weight of \(T''\) is less than or equal to the weight of \(T\). Since \({\bf{w}}({{\bf{e}}_{{\bf{k + 1}}}}) \le w({e^r})\)

\(w(T'') \le w(T)\)

Thus \(T''\) containing the edges \({{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}{\bf{,}}{{\bf{e}}_{{\bf{k + 1}}}}\) is then also a minimum spanning tree. We then derived a contradiction as we assumed that \({\bf{k}}\) was the largest possible value for which \({{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}\) is a minimum spanning tree (and we now obtained that \({{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}{\bf{,}}{{\bf{e}}_{{\bf{k + 1}}}}\) also forms a minimum spanning tree).

This then means that \({\bf{k = n - 1}}\), which implies \({\bf{S = T}}\) and thus then \({\bf{S}}\) is a minimum spanning tree.