Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ 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?

### 1. Minimum Spanning Trees (MSTs) Every spanning tree of a connected undirected graph with $|V|$ vertices contains exactly $|V| - 1$ edges.

When a constant $\alpha > 0$ is added to each edge weight, the total weight of any spanning tree $T$ becomes:

Because $(|V| - 1)\alpha$ is an identical constant added to the weight of every spanning tree, the relative ordering of tree weights is completely preserved. Therefore, any spanning tree that was an MST before the addition remains an MST after the addition.

---

### 2. Shortest Paths (SPs) Unlike spanning trees, different paths between a pair of vertices can have different numbers of edges (hops).

If path $P_1$ has $k_1$ edges and path $P_2$ has $k_2$ edges, their new path weights after adding $\alpha$ to each edge are:

Counterexample: Consider two paths between vertices $u$ and $v$:

• Path $P_1$: consists of $2$ edges, each of weight $1$ (total weight $= 2$).

• Path $P_2$: consists of $1$ edge of weight $3$ (total weight $= 3$).

Initially, $P_1$ is the shortest path since $2 < 3$. If we add $\alpha = 2$ to each edge:

• $w^{\prime}(P_1) = (1+2) + (1+2) = 6$

• $w^{\prime}(P_2) = 3 + 2 = 5$

Now $P_2$ is shorter than $P_1$, so the shortest path changes. Thus, SPs need not remain SPs.

Hence, (C) is the correct statement.