Topic summary · Student revision
Matchings Topic Review summary
Self-review on bipartite matchings, alternating paths, and the maximum matching algorithm.
Files: Topic-Review-Matchings.pdf · Topic-Review-Matchings-Answers.pdf · free public downloads · diagrams in the PDFs
Key learning points
- Bipartite graph: vertices split into two sets with edges only between sets.
- A matching pairs vertices with no shared endpoint.
- Alternating / augmenting paths improve a matching.
- Apply the maximum matching algorithm systematically from an incomplete matching.
- State the final matching as explicit pairs.
Worked example 1 — Augment
What does an augmenting path do?
Working
Flip matched/unmatched edges along the path.
Worked example 2 — Complete
When is a matching complete?
Working
Also called a perfect matching when both sets equal.
Worked example 3 — Practice point 1
Apply this idea from the Topic Review: Bipartite graph: vertices split into two sets with edges only between sets.
Working
Attempt without notes, then check the answers PDF.
Worked example 4 — Practice point 2
Apply this idea from the Topic Review: A matching pairs vertices with no shared endpoint.
Working
Attempt without notes, then check the answers PDF.
Scaffolded Learning Sheet and answers (PDFs)
This page is a short, searchable overview for revision and search engines. Use the Scaffolded Learning Sheet first, then the Answers PDF for a full written solution. The printable PDFs remain the main classroom resource.