1 The famous fictional detective Agatha Parrot is investigating a murder. She has identified six suspects: Mrs Lemon $( L )$, Prof Mulberry $( M )$, Mr Nutmeg $( N )$, Miss Olive $( O )$, Capt Peach $( P )$ and Rev Quince $( Q )$. The table shows the weapons that could have been used by each suspect.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
\multicolumn{8}{|c|}{Suspect} \\
\hline
 &  & $L$ & M & $N$ & $O$ & $P$ & $Q$ \\
\hline
Axe handle & A &  & ✓ & ✓ &  &  & ✓ \\
\hline
Broomstick & $B$ &  & ✓ &  & ✓ &  &  \\
\hline
Drainpipe & D & ✓ &  & ✓ &  &  &  \\
\hline
Fence post & $F$ &  &  & ✓ & ✓ &  &  \\
\hline
Golf club & $G$ & ✓ &  &  &  & ✓ & ✓ \\
\hline
Hammer & $H$ & ✓ &  &  & ✓ & ✓ &  \\
\hline
\end{tabular}
\end{center}

(i) Draw a bipartite graph to represent this information. Put the weapons on the left-hand side and the suspects on the right-hand side.

Agatha Parrot is convinced that all six suspects were involved, and that each used a different weapon. She originally thinks that the axe handle was used by Prof Mulberry, the broomstick by Miss Olive, the drainpipe by Mrs Lemon, the fence post by Mr Nutmeg and the golf club by Capt Peach. However, this would leave the hammer for Rev Quince, which is not a possible pairing.\\
(ii) Draw a second bipartite graph to show this incomplete matching.\\
(iii) Construct the shortest possible alternating path from $H$ to $Q$ and hence find a complete matching. Write down which suspect used each weapon.\\
(iv) Find a different complete matching in which none of the suspects used the same weapon as in the matching from part (iii).

\hfill \mbox{\textit{OCR D2 2010 Q1 [6]}}