Let $G = (V, E)$ be a weighted graph in which each edge has a positive integer cost $c_e$ and every cost is different from another. Let $G^+ = (V, E)$ be the same graph in which, however, every edge $e$ has cost $c_e+2$.
How can I prove that if $T$ is a minimum spanning tree (MST) for $G$, then $T$ is also a MST for $G^+$?
On
Let $G = (V,E,\ell)$ be the graph with the original length function, let $G^+ = (V,E,\ell^+)$ be the graph where the length of each edge is increased by 2.
Note that, (A) given any spanning tree $T$ in $G$ with total length $\ell(T)$, that same spanning tree $T$ is $G^+$ has length $\ell^+(T)= $ $\ell(T) + 2(n-1)$ in $G^+$, where $n$ is the number of vertices in $G$ and $G^+$, and vice versa (A$'$); given any spanning tree $T$ in $G^+$ with total length $\ell^+(T)$, that same spanning tree in $G$ has length $\ell(T)=$ $\ell^+(T)-2(n-1)$ in $G$. So this implies the following: (B) let $\ell^{\min}$ be the length of the minimum spanning tree in $G$, then the length of the minimum spanning tree in $G^+$ is $\ell^{\min +} =$ $\ell^{\min} + 2(n-1)$. And (B$'$) letting $\ell^{\min +}$ be the minimum spanning tree in $G^+$, the length of the minimum spanning tree in $G$ is $\ell^{\min}=$ $\ell^{\min +} - 2(n-1)$. [So $\ell^{\min +} = \ell^{min} + 2(n-1)$]
So now $T^{\min}$ be a minimum spanning tree of $G = (V,E,\ell)$ [no matter how $T^{\min}$ was found or if it is a unique minimum spanning tree]. Then $T^{\min}$ has length $\ell^{\min}$ in $G$, and so by (A) has length $\ell^{\min}+2(n-1)$ in $G^+$. However, B implies that this is also a minimum spanning tree in $G'$. Likewise, let $T^{\min +}$ be a minimum spanning tree in $G$. Can you show that $T^{\min +}$ is also a minimum spanning tree in $G$, using (A$'$ )and (B$'$)?
Hint:
1) First prove that graphs with distinct edge weights have a unique MST.
2) Suppose $T$ is not a MST in $G^+$. Show how this implies there is another MST in $G$.