1 A TV soap opera has five main characters, Alice ( $A$ ), Bob ( $B$ ), Charlie ( $C$ ), Dylan ( $D$ ) and Etty ( $E$ ). A different character is scheduled to play the lead in each of the next five episodes. Alice, Dylan and Etty are all in the episode about the fire ( $F$ ), but Bob and Charlie are not. Alice and Bob are the only main characters in the episode about the gas leak ( $G$ ). Alice, Charlie and Etty are the only main characters in the episode about the house break-in (H). The episode about the icy path (I) stars Alice and Charlie only. The episode about the jail break ( $J$ ) does not star any of the main characters who were in the episodes about the fire or the house break-in.\\
(i) Draw a bipartite graph to show which main characters ( $A , B , C , D , E$ ) are in which of the next five episodes $( F , G , H , I , J )$.

The writer initially decides to make Alice play the lead in the episode about the fire, Bob in the episode about the gas leak and Charlie in the episode about the house break-in.\\
(ii) Write down the shortest possible alternating path starting from Dylan. Hence draw the improved, but still incomplete, matching that results.\\
(iii) From this incomplete matching, write down the shortest possible alternating path starting from the character who still has no leading part allocated. Hence draw the complete matching that results.\\
(iv) By starting with the episode about the jail break, explain how you know that this is the only possible complete matching between the characters and the episodes.

\hfill \mbox{\textit{OCR D2 2013 Q1 [7]}}