Course contentsShow
← Computer Science
Lesson 1048 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Hall's Marriage Theorem

State and prove Hall's theorem characterizing when a perfect matching exists in bipartite graphs.

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.