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.