In my introductory algorithms class I recently learned about the Cut Lemma and how it can be used to prove correctness for many Minimum Spanning Tree algorithms like Kruskal's and Prim's.

In class, to simplify these proofs-of-correctness, we assumed that all edge weights in the graphs we were considering were distinct. This was also a helpful assumption when working with the Cut Lemma, since it guaranteed there will only be one minimum-weight crossing edge between the two disjoint sets of vertices created by the cut. In fact, we used proof-by-contradiction to prove the Cut Lemma, which required a unique minimum-weight edge.

My question is, what happens if edge weights aren't distinct? How can we still use the Cut Lemma to prove correctness for MST algorithms if we can no longer guarantee there is one minimum-weight crossing edge between the two sets of a cut? Is anything materially different?

  • $\begingroup$ If you remove an edge in a MST and add another edge of same weight without creating a cycle, it is still a MST. Since you consider crossing edges, you cannot create cycle by selecting any one of them. $\endgroup$
    – Nathaniel
    May 17 at 21:43
  • $\begingroup$ As Nathaniel is saying, if you apply Cut Lemma you will obtain another MST that has a weight less than or "equal" to the previous tree. In other words, for every minimum weight edge in the cut, there exists an MST that contains that edge. There can be multiple MSTs here. $\endgroup$ May 21 at 10:43

Your Answer

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

Browse other questions tagged or ask your own question.