Summary: A distributed algorithm for updating a minimum spanning tree when a new vertex is added to the underlying network (a connected, undirected, weighted graph) is presented. The algorithm runs asynchronously and the processor at each vertex of the network is required to know only information concerning its adjacent edges. The number of messages transmitted is bounded by \(6N\) and the time complexity is \(O(H)\) where \(N\) and \(H(\leq N)\) are the number of vertices and the height of the original minimum spanning tree, respectively. Each message contains at most an edge weight and a few bits. This result is superior to the previously known result as well as that of using the best known distributed minimum spanning tree algorithm to construct a minimum spanning tree for the new network from scratch. The algorithm is extended to handle \(k(\geq 1)\) vertex insertions. The resulting time and message complexities are \(O(k^*\max (H,H_ 1,\dots,H_{k-1}))\) and \(O(kN+k^ 2)\), respectively, where \(H_ i\) is the height of the MST after \(i\) new vertices have been handled. The algorithm can be modified to handle edge insertions within same time and message bounds.