How to restore a broken minimal spanning tree? We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be the graph which we get after removing $e^*$ ($E'=E\setminus \{e^*\}$). $G'$ is also connected. 


I need to propose an algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$.

I'm really not sure if I'm in the right direction but this is what I thought of:

Let $e^*=(u,v)$. 

a) We mark $e^*$ and remove it from $T$ and b) find the connected component of node $v$ by using BFS algorithm on $T$.

Now we have 2 connected components:


the first starts from $v$ let's call it $S = T\setminus e^*$
the second is $V\setminus S$


Clearly $e^*\notin S$ and $e^* \notin V\setminus S$. Also $S\neq V$ because otherwise we'd get a connected graph after the removal of $e^*$ of $n-1$ edges which would mean that there were $n$ edges in $T$ which is a contradiction since $T$ is a tree. 

c) Then we start looking for a minimal edge $e'$ from $u\in V\setminus S$ to $v\in S$. 

d) Once we found  $e'$ we'll add it to $T$ and we'll get $T'$.

I'm having trouble with running times.

a) we need to traverse $G$ in order to find $e^*$ so it's the running time of BFS which is $O(|E|+|V|)$ and because $G$ is connected ($|E| \ge |V|-1$) then the time is $O(|E|)$.

b) BFS again so $O(|E|)$.

c) This could also be $O(|E|)$ because in the worst case the graph could be something like this:


d) is O(1).
This is just to confirm that OP has, in the course of updating his question, arrived at a well-written correct "algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$".