# If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? [duplicate]

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:

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?

• Indeed, "deleting this heaviest edge yields a MINIMUM spanning tree" is not proved in either of the two posts you mentioned. A simple proof can be given if we can use the fact that the add-non-heavy-edge algorithm generates all MSTs and only MSTs. Here is the description of that algorithm. Let $G$ be a weighted graph. Start with an empty set. Iterate over all edges. Each edge is added to the set and, if a cycle is formed, remove one of its heaviest edges from the set. Feb 11 '20 at 14:21