Course contentsShow
← Mathematics
Lesson 2700 of 3,12153. Graph TheoryFree lesson

Hall's Marriage Theorem

State and prove Hall's theorem for the existence of perfect matchings in bipartite graphs using the marriage condition.

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.