[Math] The output of Kruskal’s algorithm is a spanning tree

algorithmscomputer sciencegraph theory

I want to show that the output of Kruskal's algorithm is a spanning tree.

Let $G$ be a connected, weighted graph and let $S$ be the subgraph of $G$ which is the output of the algorithm. $S$ cannot form a cycle and $S$ must be connected, since the first edge that unite two components of $S$ would have been added by the algorithm.

So, we conclude that $S$ is a spanning tree of $G$.

Is this a complete and correct justification? Can I change something to make it better?

Best Answer

To prove the correctness of Kruskal's algorithm, we need to prove that it generates a spanning tree and that this spanning tree is minimal. Let $S$ be the subgraph of $G$ which is the output of Kruskal's algorithm.

First we show that it generates a spanning tree. A spanning tree must be

  1. connected and
  2. be acyclic.

$S$ must be connected (and contain all vertices of $G$), because otherwise the algorithm wouldn't have terminated. Furthermore, $S$ must be acyclic, because each time an edge is added, that edge must not create cycles. Hence, Kruskal's algorithm produces a spanning tree.

Next we show that this spanning tree is minimal. Assume towards a contradiction that $S$ is not minimal. Then there must exist a minimum spanning tree (MST) with edges that are not in $S$. Pick the MST with the least number of edges that are not in $S$ and call this $T$.

Now consider the edge $e$ which was the first edge to be added to $S$ by Kruskal's algorithm and which is not in $T$. Then $T \cup \{e\}$ must contain a circuit, and since $S$ has no circuits, one of the edges in the circuit must not be in $S$. Call this edge $f$. Then $T' = (T \cup \{e\}) \setminus \{f\}$ is also a spanning tree.

Since $T$ is a MST, we have that $w(e) \geq w(f)$. Also, since $e$ was chosen by Kruskal's algorithm, it must be of minimal weight, so $w(e) \leq w(f)$, which in turn implies that $w(e) = w(f)$. Hence, $T'$ is also a MST, but it has one more edge in common with $S$ than does $T$, but we had chosen $T$ such that it had the most number of edges in common with $S$, so we arrive at a contradiction. We conclude that $S$ is minimal.

Related Question