Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G.
I) Check if T remains a MST or not. II) If not, give an efficient algorithm to find the minimum spanning tree of the graph G + e.
Your current MST T contains n-1 edges. The addition to your graph of the new edge e = (u,v) with weight w creates exactly one cycle C in the graph T + e (T with edge e added). If the new edge weight (w) is less than the weight of the highest-weight edge in this cycle C, then you can create a lower weight MST by replacing that higher-weight edge with e. Otherwise, your current MST remains optimal.
The algorithm is basically this:
P from u to v in Te* in P that has maximum weight w*w < w*?
T' = T - e* + e is the MST for G + e,weight(T') = weight(T) - w* + wT' = T is the MST of G + e