Hall's Marriage Theorem
What You'll Learn
You'll learn how Hall's Marriage Theorem guarantees when a bipartite graph has a perfect matching—a complete pairing between two sets.
The Marriage Problem Setup
Imagine a group of people who want to marry partners from another group, where each person has a list of acceptable partners. Hall's Marriage Theorem answers: When can everyone be matched to an acceptable partner?
In graph theory terms: Given a bipartite graph G = (X ∪ Y, E) where we want to match every vertex in X to a distinct vertex in Y, when does a perfect matching exist?
Hall's Condition (The Marriage Condition)
For any subset S ⊆ X, let N(S) denote the neighborhood of S—all vertices in Y adjacent to at least one vertex in S.
Hall's Condition: For every subset S ⊆ X, we need |N(S)| ≥ |S|.
In plain English: Every group of people must collectively know at least as many potential partners as there are people in the group.
Hall's Marriage Theorem
Theorem: A bipartite graph G = (X ∪ Y, E) has a matching that covers all of X (a perfect matching from X to Y) if and only if Hall's condition holds.
Proof Sketch
Necessity (⇒): If a perfect matching exists, then for any S ⊆ X, those |S| vertices must be matched to |S| distinct vertices in Y. Thus N(S) must contain at least those |S| vertices, so |N(S)| ≥ |S|.
Sufficiency (⇐): (By induction on |X|) Assume Hall's condition holds. We can construct a matching by carefully selecting edges, ensuring we never "trap" any vertex. If Hall's condition is satisfied, no subset can become unmatchable during construction.
Key Takeaway: Hall's Marriage Theorem states that a bipartite graph has a perfect matching from X to Y if and only if every subset S of X has at least |S| neighbors in Y.