Could someone please help me understand lines 5, 6 and 7 in the below proof for Prim's / Kruskal's greedy algorithm of finding minimum spanning tree:
Suppose that either algorithm produces a tree T. Let there exist another spanning tree S with a smaller total weight. Let e be an edge of smallest weight which lies in T but not S.
If we add e to S, we obtain a cycle, from Equivalent Definitions for Tree.
5 – This cycle contains an edge e' which is in S but not T, otherwise T would not be a tree.
6 – So, we replace e' in S with e from T, and obtain a new spanning tree S'.
7 – From the method of construction of T, it follows that the weight of e can not exceed that of e'.
So the total weight of S' does not exceed the total weight of T. Also, S' has one more edge in common with T than S has. We repeat the above procedure, and repeatedly change edges of S for edges of T, and each time the weight of the intermediate graph does not exceed that of T. Thus the weight of T does not exceed that of S, contradicting the definition of S. Hence T must be a minimum spanning tree.
My questions deal with points 5, 6, 7:
5 – If T has e', why is it not a tree?
6- Why does replace e' by e create a new spanning tree and not a new graph?
7- What make sure that w(e) <= w(e')?
Thank you.
Best Answer
Line $5$: It's a cycle. If all its edges are in $T$, that means $T$ has a cycle, and trees don't have cycles.
Line $6$: A spanning tree is a graph.
Line $7$: Since $e'$ is not in $T$, it was not added because its two vertices were already connected. But if $w(e)\gt w(e')$, then this connection could not have been through $e$, since $e$ wouldn't have been added yet, so the cycle (minus $e'$) would constitute a second connection between the two vertices of $e'$, thus forming a cycle, whereas $T$ is a tree and has no cycles.