Hall's Marriage Theorem

A bipartite matching saturates X exactly when |N(S)| ≥ |S| for all S.

The idea

Theorem (Hall's Marriage Theorem).

Let $G$ be a bipartite graph with parts $X$ and $Y$. Then $G$ has a matching that saturates $X$ if and only if $|N(S)| \ge |S| \quad \text{for every } S \subseteq X.$

The terms: $G$ is bipartite with parts $X$ and $Y$ when its vertices split into those two sets and every edge joins a vertex of $X$ to a vertex of $Y$. A matching is a set of edges no two of which share a vertex, and it saturates $X$ when every vertex of $X$ is an endpoint of a matching edge. For a set $S \subseteq X$, the neighborhood $N(S)$ is the set of vertices of $Y$ adjacent to at least one vertex of $S$.

The condition is necessary: a matching gives the members of $S$ distinct partners in $Y$, and those $|S|$ partners all lie in $N(S)$, so $|N(S)| \ge |S|$. The content of the theorem is the converse — if no subset of $X$ outnumbers its neighborhood, a matching saturating all of $X$ exists.

Ways to work on it

• Walkthrough. Neighborhoods, the deficient set, and Hall's condition.
• Practice. Test Hall's condition on a small applicants–jobs graph.
• Hardest. Find the size of a maximum matching when a perfect one is impossible.

Not sure where to start? Take the ten-question placement test.