Let 𝐺 be an edge-weighted undirected graph with positive edge weights.…

Final statement: Every minimum spanning tree remains a minimum spanning tree, and shortest paths need not remain shortest paths.

Why minimum spanning trees are unchanged:

Every spanning tree of a connected n-vertex graph has exactly n-1 edges. If a constant α>0 is added to every edge weight then the total weight of any spanning tree increases by α(n-1), the same amount for every spanning tree. Therefore comparisons of total tree weights are unchanged and any tree that was an MST before the update remains an MST after the update.

Why shortest paths can change:

The length of a path with k edges increases by kα when α is added to every edge. Different s–t paths can have different numbers of edges, so adding α can change which path has the smallest total weight. In short, paths with more edges are penalised more heavily after the update.

• Counterexample: vertices s, a, t with weights s–a = 1, a–t = 1, s–t = 3. Before adding α the path s→a→t has length 2 and is a shortest path. Choose α = 2. After adding α the weights are s–a = 3, a–t = 3, s–t = 5; the path s→a→t now has length 6 while the direct edge s–t has length 5, so the shortest path between s and t has changed.

Conclusion: The correct description is that MSTs remain MSTs under adding a constant to every edge, but shortest paths need not remain shortest paths.