5.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-6_687_1171_223_447}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}

The numbers on the $17 \operatorname { arcs }$ in the network shown in Figure 5 represent the distances, in km , between nine nodes, A, B, C, D, E, F, G, H and J.
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
\item Starting at G , use Prim's algorithm to find a minimum spanning tree. You must clearly state the order in which you select the arcs of your tree.
\item Find the weight of the minimum spanning tree.

A connected graph V has $n$ nodes. The sum of the degrees of all the nodes in V is $m$. The graph T is a minimum spanning tree of V .
\item \begin{enumerate}[label=(\roman*)]
\item Write down, in terms of $m$, the number of arcs in V .
\item Write down, in terms of $n$, the number of $\operatorname { arcs }$ in T .
\item Hence, write down an inequality, in terms of $m$ and $n$, comparing the number of arcs in T and V.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2015 Q5 [10]}}