Discrete Math › Section C · Graph theory › Topic C.9
Matching in bipartite graphs
Workers and jobs, volunteers and shifts, applicants and places: many problems ask whether each member of one group can be paired with a different acceptable member of another. Hall's theorem gives an exact test, and augmenting paths show how to build the pairing.
In this topic
- Pairing two groups
- Matchings
- What can go wrong
- Hall's theorem
- Worked example: finding the obstacle
- Alternating and augmenting paths
- Worked example: growing a matching
- Worked example: when everyone has equal choice
- Matching in practice
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…