Let’s say that I have an MST, $ T$ . I pick an edge not in $ T$ and change its weight, and add it to $ T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST?

MST means minimum spanning tree of a graph. I came across these two posts:

- https://stackoverflow.com/questions/13437702/how-to-get-the-new-mst-from-the-old-one-if-one-edge-in-the-graph-changes-its-wei
- https://sudeepraja.github.io/MST/

and I follow both until the case where $ w_{old}>w$ and $ e\notin T$ . They both say that deleting the heaviest edge will guarantee an MST, but I don’t see how to prove that. The cycle property just says that IF you have an MST, it can’t have an edge which is the heaviest edge in a cycle of the original graph $ G$ ; it is NOT saying that IF you have a tree that doesn’t contain an edge that happens to be the heaviest edge of some cycle in the original graph $ G$ , you are an MST.

To make the question more explicit in terms of the problem it was trying to solve, I will copy a part of the first link:

If its weight was reduced, add it to the original MST. This will create a cycle. Scan the cycle, looking for the heaviest edge (this could select the original edge again). Delete this edge.

I don’t understand why this guarantees that we find an MST. Sure, we get a spanning tree but why does deleting this heaviest edge yield a MINIMUM spanning tree?