title: Updating a Minimum spanning tree when a new edge is inserted
body: <p>I've been presented the following problem in University:</p>
  
  <p>Let <em>G = (V, E)</em> be an (undirected) graph with costs <em>c<sub>e</sub></em> >= 0 on the edges <em>e</em> &isin; <em>E</em>. Assume you are given a minimum-cost spanning tree <em>T</em> in <em>G</em>. Now assume that a new edge is added to <em>G</em>, connecting two nodes <em>v</em>, <em>t<sub>v</sub></em> &isin; <em>V</em> with cost <em>c</em>.</p>
  
  <ol>
  <li>Give an efficient algorithm to test if <em>T</em> remains the minimum-cost spanning tree with the new edge added to <em>G</em> (but not to the tree <em>T</em>). Make your algorithm run in time O(|E|). Can you do it in O(|V|) time? Please note any assumptions you make about what data structure is used to represent the tree <em>T</em> and the graph <em>G</em>.</li>
  <li>Suppose <em>T</em> is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(|E|)) to update the tree T to the new minimum-cost spanning tree.</li>
  </ol>
  
  <p>This is the solution I found:</p>
  
  <pre><code>Let e1=(a,b) the new edge added
  Find in T the shortest path from a to b (BFS)
  if e1 is the most expensive edge in the cycle then T remains the MST
  else T is not the MST
  </code></pre>
  
  <p>It seems to work but I can easily make this run in O(|V|) time, while the problem asks O(|E|) time. Am I missing something?</p>
  
  <p>By the way we are authorized to ask for help from anyone so I'm not cheating :D</p>