= Solution
{c}
Let $T$ be the unique <minimum spanning tree>. If $e=ab$ is an <edge> outside $T$, adding it creates a unique <graph cycle> consisting of $e$ and the <tree> <graph path> $P_T(a,b)$. Every <edge> $f$ on that <graph path> has $w(f)<w(e)$: otherwise the distinct weights would give $w(f)>w(e)$, and replacing $f$ by $e$ would produce a cheaper <spanning tree>. This is the <minimum spanning tree cycle property> in exchange form.
By the domination inequality in (i), it follows more strongly that
$$
\boxed{w(P_T(a,b))<w(e).}
$$
Now consider any simple <graph path> $P$ from $v$ to $u$ that is not the <tree> <graph path>. It must use an <edge> outside $T$. Replace every such <edge> by the corresponding <tree> <graph path>. Each replacement strictly reduces length and produces a walk entirely in $T$. Removing any repeated-vertex excursions leaves the unique <tree> <graph path> $P_T(v,u)$ and can only reduce length further. Therefore
$$
w(P_T(v,u))<w(P).
$$
So every root-to-vertex <graph path> in $T$ is the unique shortest <graph path> in $G$, and
$$
\boxed{T_{\mathrm{MST}}=T_{\mathrm{shortest},v}.}
$$
The argument works for every choice of root $v$.
Back to article page
