Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

Question

Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$ decreases by some positive number, how to prove the the MST is unchanged (still $T$) ?

It seems obvious by Kruskal's algorithm if the weight of all edges are different, if the weights are same, or some of them are same, how to prove it?

Answer 1

There is no necessarily a unique MST for a given G. So reducing an edge might trigger an MST finding algorithm to find a alternative MST. The question is if given MST remains an MST after the change.

Let's make some definitions:

• $e$ is the edge we reduce its weight
• $w(e)$ is the weight of the edge e
• $w(T)$ is the weight of tree T (sum of all edges)

I will prove it by contradiction Let's suppose that after decreasing the weight of of edge $e$ from $w(e)$ to $w'(e)$ T is no more a minimal spanning tree, and $T'$ is a minimal spanning tree.

• First we consider the case where $e \in T'$

After the decrease of w(e)-> w'(e) the new graph is $G'$. In $G'$ we have:

$w(T') < w(T)$ by assumption

$w'(e) + w(T' - {e}) < w'(e) + w(T-{e})$

$w(T'-{e}) < w(T-{e})$ and that is true both in G and G', since $\{T'-e\}$ and $\{T-{e}\}$ are same in both graphs

Then subsequently in $G$ we have $w(T'-{e}) < w(T-{e})$

$w(e) + w(T'-{e}) < w(e)+ w(T-{e})$

$w(T') < w(T)$ which means that in G T is not a minimal spanning tree which is not true.

• Now we consider the case where $e \notin T'$

Then in G' $w(T')< w(T)$ and by the same sequence

$w(T'-{e}) < w(T-e)$ in both $G$ and $G'$

In $G$ we have consequently $w(T'-{e}) + w(e) < w(T-{e}) + w(e)$ and if $T'' \equiv \{T'+e\}$ then

$w(T'') < w(T)$ which again contradicts the truth that T is MST in G.

Answer 2

Note that there isn't necessarily a unique MST, so we shouldn't talk about "the" MST of a graph. It's possible that any particular algorithm for finding an MST will come up with a different tree when you change the graph.

Let $G=(V,E,w)$ be the original weighted graph and let $G'=(V,E,w')$ be the graph made by decreasing the weight of edge $e$ by $d>0$. Because $G$ and $G'$ have the same edges, any spanning tree of one is a spanning tree of the other. Further, an spanning tree $T\subseteq G$ has weight $w'(T) = w(T)-d$ in $G'$ if $e\in T$ and weight $w'(T)=w(T)$ if $e\notin T$. Let $m$ be the weight of an MST in $G$.

If $T$ is a spanning tree of $G$, there are three cases:

1. if it is an MST of $G$ and $e\in T$, then $w'(T)=m-d$;
2. if it is an MST of $G$ and $e\notin T$, then $w'(T)=m>m-d$, so $T$ is not an MST of $G'$;
3. if it is not an MST of $G$, then $w'(T)\geq w(T)-d > m-d$, so $T$ is not an MST of $G'$.

Therefore, $T$ is an MST of $G'$ if, and only if, $T$ is an MST of $G$ and $e\in T$.

Answer 3

If the edge weights are same, and you reduce weight of an edge which was already there in the MST, then since the total weight of the old MST has even reduced than it's previous value, therefore the MST will remain the same.

But in case you reduce the edge weight of such an edge which was not there in the old MST, then the algo will be triggered to find the new MST, following which the new MST will include the modified edge.