Assume that a graph has a minimum spanning tree already computed. How fastly can the minimum spanning tree be updated if a new vertex and incident edges are added to G?
If the new vertex and the latest edges are not forming a cycle on the MST, pick up the least edge from the set of new edges. If the new vertex and the corresponding edges are producing cycle on the MST break the cycle by removing the edge with main weight. This will update the minimum spanning tree.