# MST – adding an edge to graph I have some difficulty proving the correctness of my solution to the following exercise. Let $$G = (V,E)$$ undirected connected graph, $$w \colon E \to \mathbb{R}$$ weight function. Let $$T$$ a MST (minimum spanning tree) of $$G$$. Now, we add a new edge $$e’$$ to $$E$$ with weight $$w(e’)$$. Find an algorithm that updates $$T$$ so it will be a MST of the new graph $$G’ = (V,E \cup \{e’\})$$. The time complexity of the algorithm should be $$O(V+E)$$.

Intuitively, the algorithm is quite simple: add $$e’$$ to $$T$$, and then we got one cycle closed. Remove the edge with maximal weight from this cycle, and obtain a MST of $$G’$$.

However, I had some difficulties prove the correctness of this algorithm formally, and would appriciate some help.

BTW. I have read this post: If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? but unfortunately haven’t fully got the proof there. Posted on Categories proxiesTags , ,