# Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

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? • They assume e is on a cycle in the graph, and that it is in the minimum spanning tree. They never assume the other edges on the cycle are also in the spanning tree. So it's only a cycle in the graph, not in the tree. – jmite Dec 17 '14 at 6:54
• @jmite There is another thing. The MST touches all the vertex in the graph, because it is a tree therefore connected. Then if it is connected to e, then wouldn't it necessarily have a cycle? I am having trouble drawing a MST with e but not a cycle – Carlos - the Mongoose - Danger Dec 17 '14 at 7:00
• In your picture, if e is in the MST, then only one of the other edges on V1 or Vk is in the MST. – reinierpost Dec 17 '14 at 8:34
• @reinierpost Does that mean the cycle has one edge that does not necessarily lie in MST? – Carlos - the Mongoose - Danger Dec 17 '14 at 8:39
• @IllegalImmigrant Every cycle has at least one edge that is not in any tree, since trees are acyclic by definition. – David Richerby Dec 17 '14 at 8:40