1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_522_976_351_525}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{figure}
Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below.
\begin{table}[h]
| Adele | (A) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_47_43_1210_750} | (B) | Battleship |
| Ezra | (E) | 『 | (F) | Flat iron |
| Jonah | (J) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1389_759} | (O) | Old boot |
| Lily | (L) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1486_759} | (R) | Racing car |
| Molly | (M) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_44_377_1583_759} | (S) | Scottie dog |
| Noah | (N) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_40_29_1684_764} | (T) | Top hat |
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{table}
- Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
- Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
- By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.