Adding a constant to each weight of a network does not alter its minimum spanning tree

Question

Consider a network $(G,w)$ and a function $m:E(G)\rightarrow \mathbb{R}$, with $m(e)=w(e)+c$, for every $e \in E(G)$. Show that $T$ is a minimum spanning tree of $(G,w)$ if and only if it is a minimum spanning tree of $(G,m)$. I have an idea, that adding the same constant to each weight will not alter the order of the increasing sequence of weights, so for example running Kruskal's algorithm or the reverse-delete algorithm will add (for the former) or delete (for the latter) exactly the same edges in the same order, resulting in the same tree. Is this correct or is it too simple?

Answer 1

It's correct, but it's even a little complicated for this kind of result. You could just say that, for each solution of cost $t^*$ in one problem, you can give a solution in the other problem that has a cost of $t^* \pm (|G|-1)c$ (which is the same tree, the $\pm$ depends on the direction), so the optimal solution of both are just the same with a cost differing by $\pm (|G|-1)c$.

The advantage of doing this is that you don't have to use the existence of an algorithm to solve the minimum spanning tree problem, and this kind of method translates very well to other (typically NP-complete) problems...

Moreover, in your approach, you might have problems when there are multiple solutions to the problem. Here, every solution of one problem corresponds to the solution of the translated problem, and each solution is optimal iff the translated version is optimal.