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.

-

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.

-
Thank you. I have 2 more questions: a) why does the edge swapping between S and T seem to follow the greedy algorithm. b) do you how why the author of this proof had come up with the "edge swapping" argument. –  Cody May 29 '12 at 15:12
@Cody: Unfortunately I don't understand your first question and I don't have an answer to the second one. –  joriki May 29 '12 at 18:38

If T has every e' in the cycle, then in particular is has a cycle. Trees don't have cycles. Thus it wouldn't be a tree.

It is a new graph. The graph happens to be a tree. In fact, because they chose the edge from a cycle, which has the property that every vertex has degree 2, removing 1 edge does not separate any vertex. So it is a spanning tree.

Line 7 alludes the the construction of the trees. You didn't include this here, but in all likelihood it probably has a step like "Of the available edges E, choose e of minimal weight and add it to the tree." It's probably a bit more complicated, but it's something to that effect.

-
I like that we both wrote "Trees don't have cycles." :-) –  joriki May 29 '12 at 14:11
Yes - that's very funny. –  mixedmath May 29 '12 at 14:22