0
$\begingroup$

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.

Update: I tried Steven's solution and it helped me a lot, thanks again. I also found this solution online (I add a picture), but didn't understand it well. I also don't understand why in this solution, $T'$ is the MST on $G'$ instead of a MST on $G'$. Can someone help me understand what is going on the proof there, please?A solution I found online

Improve this question
$\endgroup$
9
  • $\begingroup$ A more rigorous answer might be proving the "the delete-heavy-edge algorithm" is an MST algorithm for all cases. Somehow, a plain proof for that useful MST algorithm cannot be found (easily) on the web. $\endgroup$
    – John L.
    Commented May 24, 2020 at 19:20
  • $\begingroup$ Regarding your picture, it is likely that they are assuming that the edge weights are distinct, in this case the MST is unique. Otherwise you are right that it should have been "a MST $T'$ on $G'$ is obtained...". The proof is correct but a bit cryptic, I'll try to expand it a bit. Let $C'$ be the cycle formed by adding $e'$ to $T$. Suppose that $T'$ is not a MST of $G'$ and let $T^*$ be an actual MST of $G'$. You must have that $E(T^*) \setminus E(T) \neq \emptyset$. Then pick an arbitrary edge $e^*$ from $E(T^*) \setminus E(T)$. If you add $e^*$ to $T'$ you obtain a graph with a cycle $C$. $\endgroup$
    – Steven
    Commented May 24, 2020 at 23:49
  • $\begingroup$ If $e' \in C$ then $C$ and $C'$ differ ($C'$ contains the largest edge that cycles with $e'$ in $T$ while $C$ does not) and combining $C$ and $C'$ would yield a cycle consisting only of edges in $E(T)$, a contradiction. Therefore $e' \not\in C$. Let $e''$ be the edge having maximum weight in $C$ (assume distinct weights). $e'' \in E(T') \setminus \{e'\} \subset E(T)$ but this contradicts the minimality of $T$ in $G$ (you can get a lighter MST by replacing $e''$ with an edge from $C \setminus E(T) \neq \emptyset)$. $\endgroup$
    – Steven
    Commented May 24, 2020 at 23:49
  • $\begingroup$ Thanks. Why I must have $E(T^*) \setminus E(T) \neq \emptyset$? Also, what do you mean by "largest edge that cycles with $e'$"? $\endgroup$
    – Tom
    Commented May 25, 2020 at 0:06
  • $\begingroup$ BTW, another way I had troubles with (many ways but unfortunately with too many troubles...) is to divide into cases where $e' \in E(T')$ or not. But I'm not sure it would be easier. Maybe you could give me a direction, please? $\endgroup$
    – Tom
    Commented May 25, 2020 at 0:08

1 Answer 1

Reset to default
1
$\begingroup$

Let $T$ be the MST of the original graph $G$ and let $e'$ be the newly added edge. Suppose for simplicity that all edge weights are unique (if they are not, fix any arbitrary linear order among $E(G)$ that prioritizes the edges in $E(T)$. Then break weight ties according to this order).

Let $e$ be the edge of maximum weight in the unique cycle $C$ of $T + e'$. And assume that $e \neq e'$ (otherwise the proof is trivial).

One way to prove that $T-e+e'$ is a MST of $G+e'$ is showing that no edge $f \in \{e\} \cup E(G) \setminus E(T)$ can belong to any MST of $G+e'$ using the cycle rule.

If $f=e$, $f$ cannot belong to any MST of $G + e'$ because it is the edge of maximum weight of the cycle $C \subseteq T+e' \subseteq G + e'$.

If $f \in E(G) \setminus E(T)$ then, since $f \not\in E(T)$, $f$ must be the edge of maximum weight of some cycle $C' \subseteq G \subset G + e'$ and hence it cannot belong to any MST of $G + e'$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot, I think that I got it now. $\endgroup$
    – Tom
    Commented May 24, 2020 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.