Updating Minimum Spanning Trees

Let G be an edge-weighted, undirected, and connected graph. You are already given the MST, T, of G. Give an algorithm to update the MST when the weight of a single edge e G is increased, producing a new graph G0 . Specifically, the input is the edge e and its new weight, and your algorithm should modify T so that it is an MST in G0 , and do so in O(|V | + |E|) time. Useful Fact from class: The min weight edge across any vertex bi-partition must be in the MST. Moreover, (the removal of) any edge e in the MST induces a bi-partition, call it B(e), and so e must be the minimum weight edge across B(e). A rigorous proof is not required though please explain your answer.