= Solution
{c}
Use a triangle with <graph vertices> $v,a,b$ and <edge> weights
$$
w(va)=2,\qquad w(ab)=3,\qquad w(vb)=4.
$$
Its unique <minimum spanning tree> is $\{va,ab\}$, of cost $5$, because the other two spanning-tree costs are $6,7$. In this <tree> the $v$-to-$b$ <graph path> has length $2+3=5$, whereas the <edge> $vb$ gives length $4$ in the original <graph>. Therefore
$$
\boxed{T_{\mathrm{MST}}=\{va,ab\}\ne T_{\mathrm{shortest}}=\{va,vb\}.}
$$
Since the <minimum spanning tree> is unique, none is a <shortest-path tree> rooted at $v$.
Back to article page
