# The Edge Set Grown in Kruskal's Algorithm

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

-
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. – Alexander Gruber Feb 24 at 18:20
You're right. I forgot to mention that T' doesn't contain any cycles – Robert777 Feb 24 at 18:25
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? – Alexander Gruber Feb 24 at 19:14
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. – Robert777 Feb 24 at 19:32

1
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. – Alexander Gruber Feb 24 at 20:09
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 4, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9428656101226807, "perplexity_flag": "middle"}