We will now consider the problem of updating a minimum spanning tree. Assume that you have a graph G = (V, E) with weight function w: E R, for which you computed a minimum spanning tree T. Denote the number of edges and vertices in G by n = |V | and m = |E|.

An edge e = (u, v) with weight w(e) is now added to G to get a new graph G. Find an O(n) time algorithm to update T and obtain the minimum spanning tree T for G. Prove that your algorithm is correct, and show that it runs in the specified time.