On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows: Cycle Property:  For any cycle C in the graph, if the weight of an edge e of C is  larger than the weights of all other edges of C, then this edge cannot  belong to an MST.Proof: Assume the contrary, i.e. that e belongs to an MST T1. Then  deleting e will break T1 into two subtrees with the two ends of e in  different subtrees. The remainder of C reconnects the subtrees, hence  there is an edge f of C with ends in different subtrees, i.e., it  reconnects the subtrees into a tree T2 with weight less than that of  T1, because the weight of f is less than the weight of e.Why does the proof assume that e belongs to MST? If e belongs to a cycle, and it belongs to MST, doesn't it immediately imply that the MST has a cycle and therefore is not a tree?Please show me why I am not understanding this proof correctly. i.e. How can we have an edge e already in the tree but the tree remains acyclic?
Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?
correctness proof;spanning trees
First off to answer your main question: there is no flaw in the proof. The point where you are not following the reasoning of the proof is that:E belongs to a cycle in the graph and to the MST. Not every other edge of the cycle are in the MST. If you look at your drawing, then either one of the edges towards the rest of the MST is redundant. Because not all edges of the cycle are in the graph results in that if you remove E you get two subtrees.To answer your question about why the proof begins with assuming that e belongs to the MST: Proof by contradiction starts with assuming the opposite of what you are trying to proof. Then you reason with that assumption until you run into a contradiction.A contradiction means that your assumption must be false. If you assumption is false, then the opposite of your assumption is true.If you just look for images and MST examples there are enough examples with a cycle. Try to follow the reasoning of the proof and you will see why it is sound.