4.

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

[The total weight of the network is 2090]
\begin{enumerate}[label=(\alph*)]
\item Explain why a network cannot have an odd number of vertices of odd valency.

Figure 4 represents a network of 13 roads in a village. The number on each arc is the length, in metres, of the corresponding road. A route of minimum length that traverses each road at least once needs to be found. The route may start at any vertex and finish at any vertex.
\item Write down the vertices at which the route will start and finish.\\
(1)

A new road, AB , of length 130 m is built. A route of minimum length that traverses each road, including AB , needs to be found. The route must start and finish at A .
\item Use the route inspection algorithm to find the roads that will need to be traversed twice. You must make your method and working clear.
\item Calculate the length of a possible shortest inspection route.

It is now decided to start and finish the inspection route at two distinct vertices. A route of minimum length that traverses each road, including AB , needs to be found. The route must start at A .
\item State the finishing point so that the length of the route is minimised. Calculate how much shorter the length of this route is compared to the length of the route in (d). You must make your method and calculations clear.\\
(3)
\end{enumerate}

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