Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged 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?
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') &lt; w(T)$ by assumption

$w'(e) + w(T' - {e}) &lt; w'(e) + w(T-{e})$

$w(T'-{e}) &lt; 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}) &lt; w(T-{e})$

$w(e) + w(T'-{e}) &lt; w(e)+ w(T-{e})$

$w(T') &lt; 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')&lt; w(T)$ and by the same sequence 

$w(T'-{e}) &lt;  w(T-e)$ in both $G$ and $G'$

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

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