Let G = (V, E) be a weighted, connected and undirected graph. Let T be the edge set that is grown in Kruskal's algorithm and stopped after k iterations (so T might contain less than |E|-1 edges). Let W(T) be the weighted sum of this set. Let T’ be an acylic edge set such that |T| = |T’|. Prove that W(T) <= W(T’)

I understand the original proof of the algorithm and I’ve tried several approaches to tackle this, neither worked.

For example: I thought an induction on |T| might work. For |T| = 1 it’s obvious.

We assume correctness for |T|=k and prove (or not…) for k+1. Assume by contradiction that there exists an edge set T’ such that |T’|=k+1 and W(T’) < W(T).

Let e be the last edge added by Kruskal algorithm. So for any edge f in T’, W(f) < W(e) (otherwise we remove the edges from the 2 sets and get a contradiction).

This can only happen if every edge in T’ is already in T or forms a cycle with T – {e}.

I have no idea what to do next. I would really appreciate any help, Thanks in advance

  • $\begingroup$ This isn't true unless $T^\prime$ is (the edgeset of) a spanning tree. You say you understand the original proof of the algorithm, but I don't see how that is possible if you can't answer this question. $\endgroup$ – Alexander Gruber Feb 24 '13 at 18:20
  • $\begingroup$ You're right. I forgot to mention that T' doesn't contain any cycles $\endgroup$ – Robert777 Feb 24 '13 at 18:25
  • $\begingroup$ So how did it work in the original proof of Kruskall? How did you know at the end that the spanning tree it produces was really minimal? $\endgroup$ – Alexander Gruber Feb 24 '13 at 19:14
  • $\begingroup$ You can show that at each stage of the algorithm, when an edge e is added to the grown edge set, then the new set is contained in at least one minimal spanning tree. $\endgroup$ – Robert777 Feb 24 '13 at 19:32
  • 1
    $\begingroup$ Right, so my suggestion is this: put your edges in order by weight, smaller first, and prove that at the $k$th step, having $W(T^\prime)<W(T)$ would produce a contradiction because $T^\prime$ would have been selected by the algorithm as the smaller spanning tree. Think about when the last edge could have been added. $\endgroup$ – Alexander Gruber Feb 24 '13 at 20:09

Your Answer

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

Browse other questions tagged or ask your own question.