This was an exam question that i recently came across. Would appreciate if someone could give me an answer.
Exact Question : Given a Minimum spanning tree (MST) for an edge-weighted graph G, suppose that an edge in G, which does not disconnect G, is deleted. Describe how to find the MST of the new graph. ?
First things first, if that edge is not in your Minimum Spanning Tree, then you obviously don't need to do anything.
Let's suppose the deleted edge was in the MST. After the deletion, that leaves you with two connected components SubMST1 and SubMST2. Now to get the new MST you have to find the edge with minimum weight linking these two components. The cut property guarantees that this edge is necessarily in the MST of the new graph. The fact that the deleted edge did not disconnect the graph proves the existence of the said edge.
A simple pass through the edges would allow you to identify it (worst case complexity is O(E), assuming you can check in constant times if the source and target of an edge lies in a given set of vertices - reasonable if you use hash tables).