4. This question should be answered on the sheet provided.
The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.
| Minister | Government Position |
| \(P\) | Chancellor ( \(C\) ) |
| \(Q\) | Foreign Secretary ( \(F\) ), Minister for Education ( \(E\) ) |
| \(R\) | Minister for Defence ( \(D\) ), Minister for Industry ( \(I\) ) |
| S | Minister for Defence ( \(D\) ), Home Secretary ( \(H\) ) |
| \(T\) | Home Secretary (H) |
| \(U\) | Chancellor ( \(C\) ), Foreign Secretary ( \(F\) ) |
- Draw a bipartite graph to model this situation.
Initially the Prime Minister matches Minister \(P\) to the post of Chancellor, \(Q\) to Foreign Secretary, \(R\) to Defence and \(T\) to Home Secretary.
- Draw this initial matching.
- Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used.
Minister \(U\), on reflection, now expresses no interest in becoming Foreign Secretary.
- Explain why no complete matching is now possible.
(2 marks)