3. At a water sports centre there are five new instructors. Ali (A), George ( $G$ ), Jo ( $J$ ), Lydia ( $L$ ) and Nadia $( N )$. They are to be matched to five sports, canoeing $( C )$, scuba diving $( D )$, surfing $( F )$, sailing ( $S$ ) and water skiing ( $W$ ).

The table indicates the sports each new instructor is qualified to teach.

\begin{center}
\begin{tabular}{ | c | c | }
\hline
Instructor & Sport \\
\hline
$A$ & $C , F , W$ \\
\hline
$G$ & $F$ \\
\hline
$J$ & $D , C , S$ \\
\hline
$L$ & $S , W$ \\
\hline
$N$ & $D , F$ \\
\hline
\end{tabular}
\end{center}

Initially, $A , G , J$ and $L$ are each matched to the first sport in their individual list.
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
\item Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must clearly list any alternating paths used.

Given that on a particular day $J$ must be matched to $D$,
\item explain why it is no longer possible to find a complete matching.\\
\includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-4_720_1305_391_236}

Figure 2 models an underground network of pipes that must be inspected for leaks. The nodes $A$, $B , C , D , E , F , G$ and $H$ represent entry points to the network. The number on each arc gives the length, in metres, of the corresponding pipe.

Each pipe must be traversed at least once and the length of the inspection route must be minimised.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2002 Q3 [7]}}