4
$\begingroup$

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?

enter image description here

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – jmite Dec 17 '14 at 6:54
  • $\begingroup$ @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 $\endgroup$ – Carlos - the Mongoose - Danger Dec 17 '14 at 7:00
  • $\begingroup$ In your picture, if e is in the MST, then only one of the other edges on V1 or Vk is in the MST. $\endgroup$ – reinierpost Dec 17 '14 at 8:34
  • $\begingroup$ @reinierpost Does that mean the cycle has one edge that does not necessarily lie in MST? $\endgroup$ – Carlos - the Mongoose - Danger Dec 17 '14 at 8:39
  • 2
    $\begingroup$ @IllegalImmigrant Every cycle has at least one edge that is not in any tree, since trees are acyclic by definition. $\endgroup$ – David Richerby Dec 17 '14 at 8:40
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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