title: Finding a Minimum Spanning Tree given the old MST and a new vertex + edges
body: <p>In a sample problem, I'm given a MST T for a weighted graph G = (V, E). The question is, if a new vertex v and all its edges are to be added to the graph, what is an o(|V|log|V|) algorithm to compute the new MST of this new G* = (V U v, E*).</p>
  
  <p>My only idea so far is:</p>
  
  <pre><code>add min( out(v) ) to T
  for each edge e in out(v) do
    let u be the other vertex of e
    if there exists a lower weight path from v to u then
      remove all edges in that path from T
      add e to T
  </code></pre>
  
  <p>Two problems:</p>
  
  <ol>
  <li>What do I do with the vertices that may have gotten disconnected</li>
  <li>This is definitely not O(|V|log|V|)</li>
  </ol>
  
  <p>How can I do this?</p>