Matchings and Hall's Theorem
Decide when every element of one side can be paired off, and prove that the obvious obstruction is the only one.
What a learner can do afterwards
- State Hall's condition and check it on a small bipartite graph
- Prove that Hall's condition is sufficient, not merely necessary
- Recast an assignment problem as a matching and read off what blocks a full pairing
1 · Read
Split the world into two sides with edges only across: applicants to jobs, students to projects. A matching pairs left vertices to distinct right neighbours, and a full one covers every left vertex. The Hall condition checks every group of left vertices for enough collective neighbours. With 4 applicants there are 15 nonempty groups to examine.
One tight group decides everything. If some group jointly suits too few jobs, Hall fails and no full pairing exists: that group is the blocking set. With A and B both suiting only X, the pair A and B shares a single job and the deal is dead. When Hall holds for every group, a full pairing is guaranteed, which is why the condition is sufficient and not merely necessary.
To build the pairing, start from an unmatched applicant and walk along unused then used edges. On reaching an unmatched job, flip the path and gain one pair. Repeat until nobody is left or no such path exists. Failure certifies a Hall violator: the fenced in group you could reach.
Test groups, never single people. A lone applicant can look fine while a pair quietly shares one job. Always merge the suits of the whole group before you count.
Check every group for enough jobs, then pair off or name the blocking group.
2 · Watch
Take it off screen
Where it sits
This opens up
Nothing builds on it yet.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.