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?

Question

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?

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?

Answer 1

Your line "IF you have an MST, it can't have the heaviest edge in a cycle" is a little odd. If you have a tree (including an MST), it can have no cycles. Consequently no edge (including the heaviest edge) can be in a cycle.

Suppose that you have a tree, $T$, a subgraph of a graph, $G$, that $e$ is an edge of $G$ with vertices $a$ and $b$, and that adding $e$ to $T$ produces a cycle.

Claim: Adding $e$ to $T$ cannot produce more than one cycle. Suppose $C_1 + e$ and $C_2 + e$ are two cycles produced by inserting $e$. Then $\{a,b\} \subset C_1 \cap C_2$ and we see $C_1 + C_2$ is a cycle in $T$. Since $T$ is a tree, there are no cycles in $T$. By contradiction, we have shown the claim.

Since $T+e$ contains only one cycle, $C+e$, deleting any edge, $f$, from $C+e$ yields graph that is an acyclic tree. The graph is acyclic because we have broken the only cycle. The graph is a tree because any path $P_1{-}f{-}P_2$ connecting two vertices can be replaced with the path $P_1{-}C{-}P_2$, preserving connectivity.

Answer 2

If you already have an MST, then any edge e you add to it will itself be guaranteed to be a maximal weight edge on the resulting cycle. If the resulting cycle had an edge that had higher weight than e, then you would be able to remove it and keep e, which contradicts your claim that we began with an MST.