Proving why decreasing an edge weight in a graph may change it's MST by one edge

Question

I'm working on understanding graphs and graph algorithms.

The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf (Q 1.D)

Describe an efficient algorithm to update the minimum spanning tree $T$ of a weighted undirected graph G when the weight of one edge $e \notin T$ is decreased.

I understand the solution and it makes sense to me intuitively that we add in that edge e to T, so $T'=T+e$ then that would make a cycle which we would just go through all the edges in the cycle and remove the one with the highest weight. This is clearly right because it's the only weight that was changed so the other choices we made about other vertices not in the cycle remain unchanged, adding e and removing the other max weight edge would then give a MST intuitively.

What I don't understand is how would I prove this algorithm still results in an MST rigorously?

I feel like since it seems obvious to me, I'm not seeing the rigorous way of explaining it. I only have the hand-wavy 'it's right because it's obviously right' explanation above which I realize is not an actual proof at all.

Answer 1

Let $T$ be the original spanning tree, and let $uv$ be the modified edge. Let $xy$ be a heaviest edge on the unique $u$-$v$-path in $T$.

Remove $xy$ from $T$ to obtain $T'$, two disconnected trees consisting of connected components $A$ and $B$. Clearly, $A$ and $B$ are minimum spanning trees of their respective sets of vertices. By the cut property, a minimum weight edge with one endpoint in $A$ and one endpoint in $B$ will be in an MST.

Hence, if $uv$ is now of a lower weight than $xy$ we add $uv$ otherwise we keep $T$ as it was.

Answer 2

Think of the vertices of $G$ to be partitioned into two sets : $V_1$ and $V_2$, where $V_1$ consists of the vertices in the cycle and $V_2$ are the remaining vertices. Now In the graph, $G\setminus V_1$, the MST is what you had before, nothing has changed since $G\setminus V_1$ has not changed. In $G\setminus V_2$, you found the MST by the cycle argument.

Now MST of the two graphs combined, consists of the union of the MST of them and a single edge connecting these two MSTs. Convince yourself, that this hasn't changed and that should complete the proof.