Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Question

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$.
Now we decrease the weight by $k$ of an edge $e$ which does not belong to $T$.

How to efficiently update $T$ to make it an MST (denoted $T'$) of $G'=(V,E,w')$, where $w'$ is the same as $w$ except that $w'(e) = w(e) - k$?

The algorithm for updating $T$ to $T'$ is easy: Adding $e$ to $T$ creates a cycle $C$ in $T$. Let $e'$ be a maximum-weighted edge in the cycle $C$. If $w(e') > w’(e)$, then $T' = T \cup \{e\} - \{e'\}$ is the MST as desired. Otherwise, $T' = T$.

I have difficulty in proving its correctness by contradiction. Suppose $T''$ is a spanning tree of $G'$ and $w'(T'') < w'(T')$.

• $e \notin T''$: we have $w(T'') = w'(T'') < w'(T') \le w(T)$. Contradicts with the fact that $T$ is an MST of $G$.
• $e \in T''$: I am stuck here.

---

Two Notes:

• The accepted answer here to the same question is too general for me to follow.

• I prefer to proofs which do not rely on any concrete MST algorithms, such as Kruskal's and Prim's algorithms. However, you don't need to prove it by contradiction or separate the two cases $e \notin T''$ and $e \in T''$ as I did.

Answer 1

Let $T$ be a minimum spanning tree of $G$. Let $e$ be the edge we modify to get $G'$, and let $T'$ be the tree computed according to the algorithm. We know that weight of $T'$ is less than or equal to the weight of $T$.

Firstly, $T'$ is a tree - we create exactly one cycle in the algorithm, and break it, so we have no cycles in $T'$.

Secondly $T'$ is a spanning tree of $G'$. Let $e'$ be the edge removed and $e''$ be the edge added in the algorithm (we have either $e'' = e'$ or $e'' = e$) . To be a spanning tree, we must have a path between every pair of vertices $u$, $v$ using only edges of $T'$. Suppose that in $T$ (which is definitely a spanning tree), the path from $u$ to $v$ did not involve $e'$, then the same path exists in $T'$. Alternatively, suppose that it did use $e'$, then there is a path (without loss of generality) from $u$ to one endpoint of $e'$ and from the other endpoint of $e'$ to $v$. There is also a path from one endpoint of $e'$ to the other endpoint via $e''$ (around the cycle), all within $T'$. Then we can construct a path from $u$ to $v$ via $e''$ in $T'$ by merging these three paths and removing the overlap (although a walk is sufficient for connectivity).

Now, the important part, we wish to prove that $T'$ is a minimum spanning tree for $G'$.

Case 1: The algorithm does not add $e$ to the tree. In this case $T' = T$. Suppose that there is a minimum spanning tree $H$ for $G'$ that is different to $T'$. If $H$ has the same weight as $T'$, we're done. Now suppose for contradiction that the weight of $H$ is less than the weight of $T'$. There must be some edge $e'$ of lowest weight that is in $H$ but not in $T'$ (there must be some edge that does better, otherwise $G$ would not be of lower weight than $T'$, moreover we can assume that the edge that does better is the lowest weight edge that's not in $T'$ - we can take any $H'$ that is a lower weight tree than $T'$ and look at the candidate for $e'$, if it is not smaller than any edge in its cycle, then either $H'$ is not an MST, or we can create a new $H'$ where we swap the $e'$ for some edge of $T'$, this process must terminate with an edge $e'$ which has the property that it is the edge that does better).

1. If $e' \neq e$, then consider the tree obtained by adding $e'$ to $T$ (note, not $T'$), and removing the highest weight edge on the cycle formed. This new tree has weight less than that of $T$ and is a spanning tree for $G$, contradicting the fact that $T$ is an MST for $G$ - so we know this can't happen.
2. If $e' = e$, consider the cycle formed by adding $e' = e$ to $T'$ (i.e. the one the algorithm considered). All other edges in the cycle have lower weight than $e'$ (otherwise the algorithm would've included $e$ as an edge), and hence must be in $H$ (as $e'$ is the lowest weight edge that is not already in $T'$), but then $H$ must contain a cycle, so isn't a tree and we have a contradiction.

Case 2: The algorithm adds $e$ to $T'$. Let $x$ be the edge in $T$ that is removed by the algorithm (and hence not in $T'$) Again assume we have another MST $H$ as before. If the weight is the same, we're happy. So assume for contradiction that $H$ has lower weight, and as before $e'$ is the lowest weight edge in $H$ that's not in $T'$. We can make similar arguments as before with $x$.

1. If $e' \neq x$, (note also that $e' \neq e$), then we can improve $T$ as before, but we know that $T$ is an MST, and recalling the property that we can assume $e'$ has lower weight that at least one edge in the cycle its addition induces, this gives a contradiction and $H$ can't exist.
2. If $e' = x$, then again $e'$ must have higher weight than all the other edges in the cycle, hence $H$ must contain all these edges and $H$ is not a tree, and we derive a contradiction.

So in every case we derive a contradiction, therefore there can be no spanning tree of lower weight that $T'$, hence $T'$ is a minimum spanning tree for $G'$.

Answer 2

Let $S$ be a spanning tree of an edge-weighted graph $G$. We call $S$ a local-minimum spanning tree of $G$ if for any edge $e$ not in $S$, $e$ is a heaviest edge in the cycle created when we add $e$ to $S$.

Let me introduce a theorem about minimum spanning tree (MST).

A spanning tree is an MST if and only if it is a local-minimum spanning tree.

A proof of the above theorem by the OP herself/himself does not rely on any concrete MST algorithm.

In another proof of the above theorem but stated differently, you can also read the reason why such a spanning tree is called "local-minimum".

The above theorem enables us to verify an MST edge by edge although MST is defined with respect to all edges together.

---

Once we are armed with the above theorem, it becomes easy to prove the correctness of the algorithm in the question. It should be, in fact, easier to construct a proof by yourself than reading the rigorous proof below.

A simple proof of the algorithm in the question

Let us reuse all notations in OP's definition of the algorithm.

Note that $T$ is a local-minimum spanning tree of $G$. To prove $T'$ is an MST of $G'$, we will show $T'$ is a local-minimum spanning tree of $G'$. There are two cases.

• when $w(e')\leq w'(e)$ and $T'=T$.

  Since the only difference between $T$ in $G$ and $T'$ in $G'$ is the weight of edge $e$, we need to check $e$ only. Since $e'$ is a heaviest edge in $C$ with $w$, the condition $w'(e) \geq w(e')$ means that $e$ is a heaviest edge in $C$ with $w'$. We are done in this case.

• when $w(e')\gt w'(e)$ and $T' = T \cup \{e\} - \{e'\}$.

  1. Let us consider $e'$. The cycle created when we add $e'$ to $T'$ is also $C$. Since $e'$ is a heaviest edge in $C$ with $w$, the new weight of $e$, $w'(e) \lt w(e')$ means that $e'$ remains a heaviest edge in $C$ with $w'$.
  2. Now let $f\neq e'$ be an edge not in $T'$. Let $D$ be the cycle created when we add $f$ to $T$. Since $T$ is an MST of $G$, $\,f$ is a heaviest edge in $D$ with $w$.
     • If $e'\notin D$, $D$ is also the cycle created when we add $f$ to $T'$. As $w$ and $w'$ are the same on $D$, $\,f$ remains a heaviest edge in $D$ with $w'$.
     • Now suppose $e'\in D$. If we replace $e'$ with all edges in $C$ other than $e'$, we get from $D$ a new cycle $D'$, which is the cycle created when we add $f$ to $T'$. Since $e'$ is a heaviest edge in $C$ with $w$, $f$ remains a heaviest edge in $D'$ with $w$. Since the only difference between $w$ and $w'$ is their values on $e$, for which we have $w'(e) \lt w(e') \leq w(f) = w'(f)$, we see that $f$ remains a heaviest edge in $D'$ with $w'$.
  3. Combining step 1 and 2, we are done in this case.

Note that both the algorithm and the proof above work well regardless whether the weight of $e$ is decreased, intact or increased.

On the equal weights of edges

It is a common practice to assume distinct weights of all edges for the sake of clearer exposition. However, this post works well with possibly equal edge-weights. In particular, we have been referring to "a heaviest edge" but never "the heaviest edge".