5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Should also claim that $S$ is spanning $\endgroup$ – Salomo Apr 26 '15 at 8:04
  • $\begingroup$ Does this mean that we have to show also that at the output tree of Kruskal's algorithm all the vertices are contained? @Salomo $\endgroup$ – user175343 Apr 26 '15 at 10:56
  • $\begingroup$ the complete proof is on wikipedia under kruskals algorithm entry here $\endgroup$ – vzn Apr 26 '15 at 15:44
  • $\begingroup$ @vzn There is the sentence "Y cannot have a cycle, being within one subtree and not between two different trees." What does it mean ? $\endgroup$ – user175343 Apr 26 '15 at 16:19
  • $\begingroup$ lol its not stated very well is it? it needs some induction there. the algorithm starts with a forest of 0-edge 1-vertex "trees" (1 for all vertices). every step of the algorithm increases the size of those (separate) trees (adding edges/ vertices) or joins two trees to form a new tree. at the end there is a single tree. maybe watch a visualization of it running & then try to describe why it always works in mathematical terms. $\endgroup$ – vzn Apr 26 '15 at 16:29
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand! Thank you @mrp ! How can we show minimality? Using contradiction? $\endgroup$ – user175343 Apr 26 '15 at 19:37
  • $\begingroup$ @user159870 There are probably multiple ways to show it, but I would do it by contradiction, yes. Roughly: Assume $S$ is not minimal and consider the MST $T$ with the least number of edges which are not in $S$. Then we can construct a spanning tree $T'$ by choosing an edge $e$ from $S$ and adding it to $T$, and removing a circuit edge $f$ from the result. Then we find that $w(e) = w(f)$, but this contradicts that $T$ was chosen so that it had the least number of edges which are not in $S$. $\endgroup$ – mrp Apr 26 '15 at 19:54
  • $\begingroup$ You say that we consider the MST T with the least number of edges which are not in S. With with the least number of edges which are not in S do you mean that the edges aren't also in S or that T has NOT the least Number of edges? Then with circuit edge do you mean an edge that creates a cycle? Why do we find that w(e)=w(f)??? $\endgroup$ – user175343 Apr 26 '15 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy