Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 8 / b

True. Every spanning tree contains precisely the vertex set $V$ by definition. Thus every minimum spanning tree has $|V|$ nodes, independently of the weights or which minimum tree is chosen.

True. Every finite tree on $|V|$ vertices has exactly $|V|-1$ edges. One proof removes a leaf and its incident edge, preserving a tree on one fewer vertex, and applies induction from the one-vertex tree. Therefore all minimum spanning trees have the same edge count.

False. Take a triangle with $w(ab)=w(bc)=2$ and $w(ac)=3$. Its unique minimum spanning tree uses $ab$ and $bc$, with total weight 4. The shortest path from $a$ to $c$ in the original graph is the direct edge of weight 3; the tree's only path has weight 4. A minimum spanning tree optimizes total tree weight, not every pairwise path length.