If the weight of edge E $e$ of an MST is decreased by $\delta$. Could total weight of MST decrease by more than $\delta$.

210 Views Asked by At

I am thinking that this could not be possible (I haven't come up with a counter example yet, maybe I'm missing a corner case), So I am trying to prove this by contradiction. Since wouldn't a decrease by greater than $\delta$ mean that our original MST was not an MST?

The question in detail: Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of edge $e$ decreases by $\delta$ (Other edges stay unchanged), as $T$ is still spanning, the total weight of a MST decrease by at least $\delta$. Could the decrease be more?

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose it can, so now you have $T'$ with a weight $w(T) - \delta - \varepsilon$.

If $T'$ doesn't include $e$, $T'$ was a spanning tree with a weight under $w(T)$ - contradiction.

So $e$ is in $T'$. Change the weight of $e$ back to $w_{\text{original}}(e)$ - now the weight of $T'$ is $w(T) - \varepsilon$, but the graph is original one, so $T'$ is a spanning tree with a weight smaller than MST. Contradiction.