Question 48

Evaluating Statement I:
If all edge weights in a connected, undirected graph $G$ are distinct, then $G$ has a unique minimum spanning tree. This is a classic theorem: by Kruskal's algorithm, at each step there is a uniquely determined minimum-weight edge that connects two components, leaving no choices that could produce alternate spanning trees of identical weight. Statement I is TRUE.

Evaluating Statement II:
By the Cut Property, for any cut $(S, V \setminus S)$ in $G$, the minimum-weight edge crossing the cut must be part of every MST of $G$.
If for every cut there is a unique minimum-weight crossing edge, assume for contradiction that there exist two distinct MSTs, $T_1$ and $T_2$ with weight $W(T_1) = W(T_2)$.
Let $e \in T_1 \setminus T_2$. Removing $e$ splits $T_1$ into two connected components, defining a cut $(S, V \setminus S)$.
Because $T_2$ is a spanning tree, there must be at least one edge $e' \in T_2$ crossing this cut.
By hypothesis, the cut has a unique minimum-weight crossing edge. If $e$ is this edge, then $w(e) < w(e')$, so $(T_2 \setminus \{e'\}) \cup \{e\}$ is a spanning tree with weight strictly less than $W(T_2)$, contradicting the minimality of $T_2$.
Hence, no two distinct MSTs can exist, and $G$ has a unique MST. Statement II is TRUE.

Both statements I and II are TRUE.