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.