1
$\begingroup$

I found the following proof for the theorem that states "A light edge that crosses a cut that respects A is safe for A": enter image description here

See: https://www2.hawaii.edu/~janst/311_f19/Notes/Topic-17.html where also all the necessary definitions are given.

What I do not understand in this proof is that we have here T that is a MST and then we say that T' is also a MST that contains the edge u-v and not x-y. But if the weight of u-v is less than that of x-y ("w(T) - w(x,y) + w(u,v) ≤ w(T)"), then T could have never been a MST (because it would have never chosen x-y over u-v)? Does someone see what goes wrong in my explanation?

$\endgroup$

1 Answer 1

1
$\begingroup$

Although correct, that statement, "$w(T') = w(T) - w(x,y) + w(u,v) \le w(T)$" alone is indeed confusing, since it leaves the impression that $w(T')$ might be smaller than $w(T)$.

Well, the equal part of "$\le$" comes to rescue. It is possible that $w(T')=w(T)$.

Indeed, that must be the case, since we also have $w(T)\le w(T')$ by the definition of MST and $T$ being an MST.

There is nothing wrong to say "$w(T')\le w(T)$", just as we say "$3\le 3$".


Furthermore, we know that $w(x,y)=w(u,v)$. This is the fact that the edge in any MST that crosses a cut must be an edge of minimum weight that crosses that cut. (All minimum edges crossing the same cut have the same weight, of course.)

$\endgroup$
3
  • $\begingroup$ Thank you, so if I'm not mistaken there could be written "w(T) - w(x,y) + w(u,v) = w(T)"? $\endgroup$ Jun 23 at 20:10
  • $\begingroup$ That is correct. $\endgroup$
    – John L.
    Jun 23 at 20:15
  • $\begingroup$ Thank you. Is there perhaps a way to also understand intuitively why this statement is true? And can I also say that once there is no such cut, then one has obtained a minimal spanning tree? Should I maybe post these questions as a separate question? $\endgroup$ Jun 23 at 20:17

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.