Hall's Marriage Theorem
You'll learn the fundamental condition that guarantees a perfect matching exists in a bipartite graph.
The Big Question
Imagine you have a set of job applicants and a set of jobs. Each applicant is qualified for certain jobs. Can you assign every applicant to a different job they're qualified for? Hall's Marriage Theorem tells you exactly when this is possible.
The Condition
Hall's Marriage Theorem states: A bipartite graph G = (X ∪ Y, E) has a perfect matching (a matching that covers all vertices in X) if and only if for every subset S ⊆ X, the neighborhood N(S)—the set of vertices in Y adjacent to at least one vertex in S—satisfies:
|N(S)| ≥ |S|
In plain English: For any group of applicants, there must be at least as many jobs they're collectively qualified for.
This is often called the marriage condition or Hall's condition.
Why It's True
Forward direction (if matching exists): If you already have a perfect matching, then any k applicants must be matched to k distinct jobs, so those k applicants collectively have access to at least k jobs.
Reverse direction (if condition holds): The proof uses augmenting paths (from max flow). If Hall's condition holds but no perfect matching exists, you can show that there must be some subset S violating the condition—a contradiction. The key insight: the condition prevents "bottlenecks" where too many vertices compete for too few neighbors.
Example
If 3 applicants are qualified for only 2 jobs total, Hall's condition fails: |N({a₁, a₂, a₃})| = 2 < 3, so no perfect matching exists.
Key Takeaway: Hall's Marriage Theorem guarantees a perfect matching exists if and only if every subset of vertices has a sufficiently large neighborhood—no group is starved for choices.