2 A father is going to give each of his five daughters: Grainne ( $G$ ), Kath ( $K$ ), Mary ( $M$ ), Nicola ( $N$ ) and Stella ( $S$ ), one of the five new cars that he has bought: an Audi ( $A$ ), a Ford Focus ( $F$ ), a Jaguar ( $J$ ), a Peugeot ( $P$ ) and a Range Rover ( $R$ ).

The daughters express preferences for the car that they would like to be given, as shown in the table.

\begin{center}
\begin{tabular}{|l|l|}
\hline
 & Preferences \\
\hline
Grainne ( $G$ ) & Audi $( A )$ or Peugeot ( $P$ ) \\
\hline
Kath ( $K$ ) & Peugeot ( $P$ ) or Ford Focus ( $F$ ) \\
\hline
Mary ( $M$ ) & Jaguar ( $J$ ) or Range Rover ( $R$ ) \\
\hline
Nicola ( $N$ ) & Audi $( A )$ or Ford Focus ( $F$ ) \\
\hline
Stella ( $S$ ) & Jaguar ( $J$ ) or Audi ( $A$ ) \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show all these preferences on a bipartite graph.
\item Initially the father allocates the Peugeot to Kath, the Jaguar to Mary, and the Audi to Nicola.

Demonstrate, by using alternating paths from this initial matching, how each daughter can be matched to a car which is one of her preferences.\\
(6 marks)
\end{enumerate}

\hfill \mbox{\textit{AQA D1 2005 Q2 [8]}}