# safe edge theorem proof clarification

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

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?

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.)

• Thank you, so if I'm not mistaken there could be written "w(T) - w(x,y) + w(u,v) = w(T)"? Jun 23 at 20:10
• That is correct. Jun 23 at 20:15
• 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? Jun 23 at 20:17