| Answer/Working | Marks | Guidance |
|---|---|---|
| A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set | B1, B1 | (2) |
| [Bipartite graph diagram shown] | B1 | (1) |
| AP1: $B - 5 = E - 6 = F - 1$ AP2: $B - 5 = E - 4 = C - 3$ AP3: $D - 2 = A - 4 = C - 3$ | M1 | |
| Change status either stated or shown | A1 | |
| IM1: $A = 2, B = 5, C = 4,$ (D unmatched) $E = 6, F = 1$ IM2: $A = 2, B = 5, C = 3,$ (D unmatched) $E = 4, F = 6$ IM3: $A = 4,$ (B unmatched) $C = 3, D = 2, E = 5, F = 6$ | A1 | |
| AP1: $D - 2 = A - 4 = C - 3$ AP2: $D - 2 = A - 4 = E - 6 = F - 1$ AP3: $B - 5 = E - 6 = F - 1$ | M1 | |
| Change status either stated or shown | A1 | |
| Complete matching: $A = 4, B = 5, C = 3, D = 2, E = 6, F = 1$ | A1 | (6) |
| | **9 marks** | |

**Notes for Question 1:**

- **a1B1**: Two sets of vertices – must contain the three words in bold. Accept nodes for vertices but not points or any other non-technical language. These three words do not need to be in the same sentence.
- **a2B1**: Edges/arcs must go from one (set) into the other – candidates must give an indication of going from one set to the other. If a candidate only says you cannot connect nodes from the same set then this is B0. As an absolute minimum accept a statement along the lines of: "arcs must go from one to the other" – note that for this mark candidates must use the word 'edge(s)' or 'arc(s)' but other technical language may be absent or incorrect.
- **b1B1**: CAO
- **c1M1**: An alternating path (e.g. letter 1st set – number 2nd set – letter 1st set – …) from B to 1 (or vice-versa) or B to 3 (or vice-versa) or D to 3 (or vice-versa)
- **c1A1**: CAO – a correct path including change status either stated (only accept 'change (of) status' or 'c.s.' but not, e.g. 'change state') or shown (all symbols e.g. $(… – … = …)$ interchanged). **Chosen path clear**
- **c2A1**: CAO – improved matching - must follow from the correct stated path. Accept either stated or on a clear diagram (with five arcs only). Please check the top of the second page as many candidates will draw either the improved or complete matching on the nodes provided there.
- **c3A1**: CAO – a correct path including change status stated or shown. **Chosen path clear**
- **c4A1**: CAO (complete matching) must follow from two correct stated paths (so both previous M marks must have been awarded). Accept on a clear diagram (with six arcs only).

A number of candidates are giving more than one alternating path in (c) - please award the marks for the alternating paths used that lead to their complete matching (so stating more than one solution can score full marks). If a candidate states two alternating paths and then only improved matching and it is not explicitly clear by the candidate's working which of the two alternating paths gives the improved matching then award M1A0A1 (for the first A mark the chosen path must be clear and not simply implied by a correct improved matching if more than one AP given). They can, however, go on and score the final three marks using a consistent alternating path from their improved matching.

**SC for (c)**: some candidates are writing AP1 and AP3 from the first list next to each other with no improved matching and so it is not clear if they are applying the algorithm correctly e.g.
- Alternating path: $D - 2 = A - 4 = C - 3; B - 5 = E - 6 = F - 1$
- Change status: $D = 2 - A = 4 - C = 3; B = 5 - E = 6 - F = 1$
- Complete matching: $A = 4, B = 5, C = 3, D = 2, E = 6, F = 1$

This would scored M1 A0 A0 M1 A0 A1 (neither chosen path is clear – are they choosing two APs from the first list or does one follow the other (reading across the page) – either way it is not clear)

---