Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant α is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?

The correct option is: Every MST remains an MST, and SPs need not remain SPs.

Let us understand why this statement is true by analyzing the effect of adding a positive constant $\alpha$ to the weight of every edge on Minimum Spanning Trees (MSTs) and Shortest Paths (SPs) separately.

1. Effect on Minimum Spanning Trees (MSTs):
Let $G=(V,E)$ be a connected undirected graph with $n=\left|V\right|$ vertices.
Any spanning tree $T$ of $G$ must contain exactly $n-1$ edges.
Let $w\left(e\right)$ be the original weight of edge $e$, and let the new weight be $w^{\prime }\left(e\right)=w\left(e\right)+\alpha$.
The total weight of a spanning tree $T$ under the new weight function $w^{\prime }$ is:

$W^{\prime }\left(T\right)=\sum _{e\in T}{w}^{\prime }\left(e\right)=\sum _{e\in T}\left(w\right(e)+\alpha )$

Since there are exactly $n-1$ edges in $T$, this simplifies to:

$W^{\prime }\left(T\right)=\left(\sum _{e\in T}w\right(e\left)\right)+(n-1)\alpha =W\left(T\right)+(n-1)\alpha$

Here, $(n-1)\alpha$ is a constant value added to the total weight of every spanning tree in the graph. Since the weights of all spanning trees are shifted by the exact same constant, the relative ordering of their weights does not change. Thus, any tree $T$ that minimized the original weight $W\left(T\right)$ will also minimize the updated weight $W^{\prime }\left(T\right)$. Therefore, every MST remains an MST.

2. Effect on Shortest Paths (SPs):
Let $P$ be a path between two vertices $u$ and $v$. The number of edges in $P$ (path length in terms of edges) can vary. Let $k$ be the number of edges in $P$.
Under the new weight function, the total weight of path $P$ becomes:

$W^{\prime }\left(P\right)=W\left(P\right)+k\alpha$

Since paths between two vertices can have different numbers of edges, adding $\alpha$ to every edge penalizes paths with more edges more heavily than paths with fewer edges. Consequently, the relative ranking of path weights can change, and a path that was previously the shortest may no longer be so.
For example, consider a graph with two vertices $u$ and $v$ connected by two alternative paths:
- Path $P_1$ has 1 edge of weight 4.
- Path $P_2$ has 2 edges of weights 1.5 and 2 (total original weight = 3.5).
Originally, $P_2$ is the shortest path since $3.5<4$.
Now, add $\alpha =2$ to every edge weight:
- New weight of $P_1$ = $4+2=6$.
- New weight of $P_2$ = $(1.5+2)+(2+2)=3.5+2\left(2\right)=7.5$.
After the update, $P_1$ becomes the shortest path ($6<7.5$). Thus, shortest paths need not remain shortest paths.