1
$\begingroup$

Question: Let G(V, E) be an undirected connected finite graph with the weight function w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of Kruskal’s algorithm that finds T (for suitable ordering of edges).

Answer: We show that the following proposition P is true by induction: If F is the set of edges chosen at any stage of the algorithm, then there is some minimum spanning tree that contains F and none of the edges rejected by the algorithm.

  • Clearly P is true at the beginning, when F is empty: any minimum spanning tree will do, and there exists one because a weighted connected graph always has a minimum spanning tree.

  • Now assume P is true for some non-final edge set F and let T be a minimum spanning tree that contains F. If the next chosen edge e is also in T, then P is true for F + e.

    Otherwise, if e is not in T then T + e has a cycle C. This cycle contains edges which do not belong to F, since e does not form a cycle when added to F but does in T. Let f be an edge which is in C but not in F + e. Note that f also belongs to T, and by P, it has not been considered by the algorithm. f must therefore have a weight at least as large as e. Then T − f + e is a tree, and it has the same or less weight as T. However since T is a minimum spanning tree then this new graph has the same weight as T, otherwise we get a contradiction and T would not be a minimum spanning tree .So T − f + e is a minimum spanning tree containing F + e and again P holds.

  • Therefore, by the principle of induction, P holds when F has become a spanning tree, which is only possible if F is a minimum spanning tree itself.

$\endgroup$
4
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – Nathaniel
    Commented Oct 5, 2023 at 16:37
  • $\begingroup$ Do you've a good reason to discourage it? It can be helpful to others who want to see similar proofs. $\endgroup$
    – Team B.I
    Commented Oct 6, 2023 at 11:30
  • $\begingroup$ @achhainsan I have literally added links with explainations. $\endgroup$
    – Nathaniel
    Commented Oct 6, 2023 at 12:55
  • $\begingroup$ Please do not delete your question after receiving an answer. This is often considered impolite. Part of our purpose here is to build up an archive of high-quality questions and answers that will be useful to others -- not just to you -- and answerers may be writing their answer on the assumption that it will help not only you but others. $\endgroup$
    – D.W.
    Commented Oct 13, 2023 at 19:05

2 Answers 2

1
$\begingroup$

To prove correctness of Kruskal's algorithm (and Prim's), you can use the cut property.

Lemma (The cut property). Let $\emptyset \subset S \subset V$ be a set of vertices and $e$ a cheapest edge with exactly one endpoint in $S$. Then there is a minimum spanning tree $T$ that contains $e$.

Proof (sketch). Let $S$ be as above and $e = uv$ a cheapest edge with $u \in S$ and $v \notin S$. Let $T'$ be an MST. If $e$ is in the tree, we are done. So assume $e$ is not in $T'$. Since $T$ is a spanning tree, there is a path from $u$ to $v$ in $T'$, and this path must leave $S$ at some point. So let $e' = u'v'$ be an edge in $T$ with $u' \in S$ and $v' \notin S$. Observe that $w(e') \geq w(e)$. Create $T = (T' \setminus e') \cup e$, the tree where we replace $e'$ with $e$.

  1. $w(T) \leq w(T')$.
  2. $T$ is spanning
  3. $T$ is a tree.

To see why the last is true, observe that we replaced one edge with another, so the number of edges is the same as in $T'$, so we only need to show that it is connected. But this holds since $u'$ is connected to $v'$ via the (already existing) $u$-$u'$-path and $v$-$v'$-path, plus the edge $e$. It follows that $T$ is acyclic and therefore a tree.

$\endgroup$
4
  • $\begingroup$ The approach in the question uses induction to prove that every edge chosen by Kruskal is contained in some MST. The approach in your answer (which is not explained, but only mentioned) uses contradiction to prove that every minimum edge weight crossing a cut is chosen by Kruskal, but I fail to see how this works without distinct edge weights or unique MST. $\endgroup$ Commented Jan 7 at 12:32
  • $\begingroup$ @KennethKho Thank you for your comment. While in its simplest form it's a proof by contradiction, it's fundamentally an exchange argument, which also explains why it works without assuming distinct edge weights or unique MST. We simply say that for any $S \subseteq V$ with $e$ any minimum weight edge with one endpoint in $S$, we can exchange some edge in $T$ leaving $S$ with $e$ while at the same time keeping (or improving) the total weight. $\endgroup$
    – Pål GD
    Commented Jan 8 at 7:53
  • $\begingroup$ Indeed, the lemma says there is a minimum spanning tree $T$ that contains $e$ a cheapest edge with one endpoint in $S$. I think I understand this short proof that uses similar exchange argument, it arrives at your lemma creating $T = (T' \setminus e') \cup e$ as a new spanning tree not costing anything more and argues we can do this for every edge that differs. The contradiction is a red herring, I think, since we don't at all need assume Kruskal's tree is not optimal, only different and exchange. Do I understand this correctly? $\endgroup$ Commented Jan 18 at 12:48
  • $\begingroup$ I would summarize OP's proof being each Kruskal step matches either the same MST as the previous step or a different MST that is MST nonetheless, and your proof being each cheapest edge replacement turns the same MST into a different MST that is MST nonetheless. Is this a correct intuition? $\endgroup$ Commented Jan 18 at 12:59
0
$\begingroup$

The proof in question is based on a Wikipedia page at the time of posting. However, the conclusion that the cycle contains edges that do not belong to $F$ is inaccurate, instead the cycle contains edges that do not belong to $F + e$. The conclusion that $f$ also belongs to $T$ is also left unexplained, which is because $f$ belongs to $T + e$ but not $F + e$. Also note that it lacks a reference. Here is an improved version of the second part, which is in the current page:

Now assume $P$ is true for some non-final edge set $F$ and let $T$ be a minimum spanning tree that contains $F$.

If the next chosen edge $e$ is also in $T$, then $P$ is true for $F + e$.

Otherwise, if $e$ is not in $T$ then $T + e$ has a cycle $C$. The cycle $C$ contains edges which do not belong to $F + e$, since $e$ does not form a cycle when added to $F$ but does in $T$. Let $f$ be an edge which is in $C$ but not in $F + e$. Note that $f$ also belongs to $T$, since $f$ belongs to $T + e$ but not $F + e$. By $P$, $f$ has not been considered by the algorithm. $f$ must therefore have a weight at least as large as $e$. Then $T − f + e$ is a tree, and it has the same or less weight as $T$. However since $T$ is a minimum spanning tree then $T − f + e$ has the same weight as $T$, otherwise we get a contradiction and $T$ would not be a minimum spanning tree. So $T − f + e$ is a minimum spanning tree containing $F + e$ and again $P$ holds.

Here is what it looks like in the more concise original 2009 page, it contains the same mistake in saying that $f$ is not in $F$ while it should say $f$ is not in $F + e$, my annotations are inside square brackets:

Now assume $P$ is true for some non-final edge set $F$ and let $T$ be a minimum spanning tree that contains $F$.

If the next chosen edge $e$ is also in $T$, then $P$ is true for $F + e$.

Otherwise, $T + e$ has a cycle $C$ [$T$ is connected] and there is another edge $f$ that is in $C$ but not $F$ [$F + e$ is acyclic]. Then $T - f + e$ is a tree [$f$ is not $e$ as $f$ belongs to $T + e$ but not $F + e$], and its weight is not more than the weight of $T$ since otherwise the algorithm would choose $f$ in preference to $e$ [$f$ is not less than $e$]. So $T - f + e$ is a minimum spanning tree [no more and no less than $T$] containing $F + e$ and again $P$ holds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.