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.
| Preferences |
| Grainne ( \(G\) ) | Audi \(( A )\) or Peugeot ( \(P\) ) |
| Kath ( \(K\) ) | Peugeot ( \(P\) ) or Ford Focus ( \(F\) ) |
| Mary ( \(M\) ) | Jaguar ( \(J\) ) or Range Rover ( \(R\) ) |
| Nicola ( \(N\) ) | Audi \(( A )\) or Ford Focus ( \(F\) ) |
| Stella ( \(S\) ) | Jaguar ( \(J\) ) or Audi ( \(A\) ) |
- Show all these preferences on a bipartite graph.
- 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)