Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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