Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges not in T. Give an algorithm for finding the MST of the updated graph.
I know the algorithm is to remove the max weight edge in the cycle, but how to explain it clearly. I think it is really hard to prove its correctness.