You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some value. You now want to come up with a smart way to find the new MST of the graph.
My approach would be the following. Take this edge
(u,v) that you changed and add it to your MST. Start from
u and travel around in your MST until you end up back in
u, since it is guaranteed that after inserting
(u,v) you will create a cycle (MST is a tree). Then from the cycle that you found, remove the edge with the maximum weight.
I feel like this is correct but I don't know how to prove it. Can someone guide me?
Here's what I've tried:
My intuition about the problem is the following. Let's call T, the MST that we found before updating an edge (u,v). Now after updating this edge (u,v), let's just add it to our MST. What is the resulting structure? Since we connect two nodes that are part of the MST with an edge that was previously not in the MST, we create a cycle. Of course this indicates that some edge/edges need to go, since what we just created is not a valid MST. We can not remove any edges that are not part of the cycle that we just created, since this action would give us two components that are not connected. If we look at the cycle that we created, we can only remove exactly one edge and no more than that. Since we want to minimize the weight of all the edges part of the MST, we simply remove the edge with the largest weight. So in the end we get something that is definitely a spaning tree, and it is also minimal. Proving that it's spanning tree is trivial. To prove the latter, the edges that are not part of the cycle, should definitely be part of some MST (they are light edges of some cut), so it's ok to leave them there, as for the cycle removing the max weight will give a min total weight.