3.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_591_1365_239_360}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}

Figure 2 shows a graph G.
\begin{enumerate}[label=(\alph*)]
\item Write down an example of a cycle on G.\\
(1)
\item State, with a reason, whether or not $\mathrm { P } - \mathrm { Q } - \mathrm { R } - \mathrm { T } - \mathrm { Q } - \mathrm { S }$ is an example of a path on G .\\
(2)

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_618_1406_1336_340}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}

The numbers on the $14 \operatorname { arcs }$ in Figure 3 represent the distances, in km , between eight vertices, $\mathrm { P } , \mathrm { Q }$, $\mathrm { R } , \mathrm { S } , \mathrm { T } , \mathrm { U } , \mathrm { V }$ and W , in a network.
\item Use Prim's algorithm, starting at P , to find the minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
\item Use Kruskal's algorithm to find the 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 the minimum spanning tree.
\item Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.

The weight on arc RU is now increased to a value of $x$. The minimum spanning tree for the network is still unique and includes the same arcs as those found in (e).
\item Write down the smallest interval that must contain $x$.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2015 Q3 [12]}}