= Solution
Start <Prim's algorithm> at <vertex> $1$, since the source does not specify a starting <vertex>. Write every undirected <edge> with its smaller endpoint first. With lexicographic tie-breaking, the accepted <edges> are \b[$(1,2),(1,3),(2,4),(4,6),(4,5)$], of total weight \b[9].
Initially $(1,2)$ is the cheapest crossing <edge>. The next minimum is a weight-two tie between $(1,3)$ and $(2,4)$, so choose $(1,3)$. Then the weight-two tie between $(2,4)$ and $(3,4)$ is resolved in favour of $(2,4)$. Adding <vertex> $4$ exposes the weight-one <edge> $(4,6)$, which is selected next. Finally $(4,5)$ precedes $(5,6)$ among the weight-three choices. Every accepted <edge> crosses from the existing tree to a new <vertex>, as required by the <minimum spanning tree cut property>. A different starting <vertex> can produce a different accepted-edge order; the displayed answer fixes that unspecified choice. The algorithm is named for <Robert C. Prim>.
Back to article page
