1 Adam, Barbara and their children Charlie, Donna, Edward and Fiona all want cereal for breakfast. The only cereal in the house is a pack of six individual portions of different cereals.
The table shows which family members like each of the cereals in the pack.
| \multirow{8}{*}{Cereal} | \multirow{2}{*}{} | Family member |
| | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) |
| Cornflakes (1) | ✓ | ✓ | | | | ✓ |
| Rice pips (2) | | | ✓ | ✓ | | |
| Wheat biscs (3) | | ✓ | | ✓ | | |
| Oatie bits (4) | | | | | ✓ | ✓ |
| Choco pips (5) | ✓ | | ✓ | | ✓ | |
| Honey footballs (6) | | ✓ | | | | |
- Draw a bipartite graph to represent this information.
Adam gives the cornflakes to Fiona, the oatie bits to Edward, the rice pips to Donna, the choco pips to Charlie and the wheat biscs to Barbara. However, this leaves the honey footballs for Adam, which is not a possible pairing.
- Draw a second bipartite graph to show this incomplete matching.
- Construct the shortest possible alternating path from 6 to \(A\) and hence find a complete matching between the cereals and the family members. Write down which family member is given each cereal with this complete matching.
- Adam decides that he wants cornflakes. Construct an alternating path starting at \(A\), based on your answer to part (iii) but with Adam being matched to the cornflakes, to find another complete matching. Write down which family member is given each cereal with this matching.