Minimum Spanning Tree (MST)

Question

Suppose $T$ is a minimum spanning tree (MST) of graph $G(V, E)$. An edge $(u, v) ∈ E$ is not in $T, (u, v) ∉ T$. Now, the weight of $(u, v)$ reduces to $w(u, v)$ so that T may be no longer an MST. Please design an $O(n)$ algorithm that modifies $T$ to obtain a new MST for graph $G$ with this change, where $n = |V|$. You need to prove its correctness

The idea is to add the reduced edge $(u,v)$ to the Tree $T$. Now, we have a cycle, and $T$ are no longer an MST. We need to modify $T$ to obtain a new MST by applying BFS on $T$ where node $u$ is the source node. While we traverse the Tree $T$ we keep track of largest edge and remove it from $T$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
T = T ∪ {e(u,v)}    # add the reduced edge to the Tree
BFS(T, s):
  e(x,y) = nil
  largest = 0
  Q = ∅       # create a queue
  Enqueue(Q,s)
  while Q not empty:
      u ← Dequeue(Q)
      for each neighbor v of u and not in Q:
            if largest < w(v,u)     # keep track of the largest edge
                largest = w(v,u)
                e(x,y) = e(v,u)
                Enqueue(Q,v)
  T = T - {e(x,y)}    # remove the largest edge from the Tree
End