Question 26

Statement (I): In any connected undirected graph where all edge weights are distinct, the Minimum Spanning Tree (MST) is unique.
Proof: Suppose there are two distinct MSTs, $T_1$ and $T_2$. Let $e$ be the minimum weight edge that belongs to one tree but not the other, say $e \in T_1 \setminus T_2$. Adding $e$ to $T_2$ creates a cycle $C$. There must be an edge $e' \in C$ that is not in $T_1$. Since all edge weights are distinct and $e$ is the minimum such edge, $w(e') > w(e)$. Replacing $e'$ with $e$ in $T_2$ produces a spanning tree of strictly smaller weight than $T_2$, contradicting the assumption that $T_2$ was an MST. Hence, the MST is always unique. Statement (I) is necessarily true.

Statement (II): Distinct positive edge weights do not guarantee that the shortest path between every pair of vertices is unique.
Counterexample: Consider a graph with vertices $\{u, v, x, y\}$ and distinct edge weights:

• $w(u, x) = 1$, $w(x, v) = 4$
• $w(u, y) = 2$, $w(y, v) = 3$
  All four edge weights are positive and distinct (1, 2, 3, 4). The path $u - x - v$ has length $1 + 4 = 5$, and the path $u - y - v$ has length $2 + 3 = 5$. Both paths between $u$ and $v$ have the exact same shortest distance 5, so the shortest path is not unique. Hence, Statement (II) is not necessarily true.

Therefore, only Statement (I) is necessarily true.