2
$\begingroup$

I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction.

We suppose that $S$ is not a minimum spanning tree.

Let $T$ be a spanning tree which has the minimum weight.

How can I go on to get a contradiction ?

$\endgroup$
  • $\begingroup$ My thought (repeated from chat) is that the algorithm requires you to choose the lowest weight edge. So if T is smaller than it, then you didn't choose the smallest edge. I feel like there's something there. Maybe it will provide food for though. $\endgroup$ – Jeff Apr 27 '15 at 3:21
0
$\begingroup$

Let the original graph $G$ have $n$ vertices. Let the $n - 1$ edges of $S$ selected by Kruskal's algorithm (in order) be $e_1, e_2, \ldots, e_{n-1}$. Out of all possible minimum spanning trees of $G$, let $T$ be a minimum spanning tree that has the largest number of edges $e_1, e_2, \ldots, e_{r-1}$ in common with the initial edges of $S$. Now suppose instead that $S$ is not a minimum spanning tree (so that $r < n$). To get our contradiction, we will construct a new minimum spanning tree $T'$ of $G$ that has an extra edge $e_r$ in common with $S$ than $T$.

By the maximality of $T$, notice that $e_r$ is in $S$ but $e_r$ is not in $T$. Now since $T$ is a tree and trees are maximally acyclic, we know that $T + e_r$ contains some cycle $C$. Hence, since $T$ does not contain any cycles (including $C$), we know that there is some edge $f$ in $C$ that is not in $T$. Consider $T' = T + e_r - f$. Since $T'$ is still connected and has exactly $n$ vertices and $n - 1$ edges, notice that $T'$ is a spanning tree of $G$. We claim that $T'$ is also a minimum spanning tree.

Indeed, consider the point in time after the edges $e_1, \ldots, e_{r-1}$ have already been selected for $S$ and Kruskal's algorithm selects the edge $e_r$. Notice that the algorithm could have selected $f$ instead of $e_r$ without creating a cycle (otherwise, if $e_1, \ldots, e_{r-1}, f$ contains a cycle, then $T$ would also contain this cycle, a contradiction). Hence, since Kruskal's algorithm chose $e_r$ instead of $f$, we know that $\text{wt}(e_r) \leq \text{wt}(f)$. Thus, it follows that: $$ \text{wt}(T') = \text{wt}(T) + \text{wt}(e_r) - \text{wt}(f) \leq \text{wt}(T) + \text{wt}(f) - \text{wt}(f) = \text{wt}(T) $$ But since $T$ is a minimum spanning tree, we know that $\text{wt}(T) \leq \text{wt}(T')$ so that equality holds. Hence, $T'$ is also a minimum spanning tree, as desired. $~~\blacksquare$

$\endgroup$

Your Answer

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