Bipartite Matching & Hall's Theorem

Saturate one side exactly when every set has enough neighbors.

The idea

A bipartite graph has its vertices split into two parts $A$ and $B$, with every edge joining a vertex of $A$ to a vertex of $B$ — applicants and jobs, say, with an edge for each acceptable pairing. A matching is a set of edges no two of which share an endpoint, and it saturates $A$ when every vertex of $A$ is an endpoint of one of its edges. For $S \subseteq A$, write $N(S)$ for the set of vertices in $B$ adjacent to at least one vertex of $S$.

Theorem (Hall's theorem).

Let $G$ be a bipartite graph with parts $A$ and $B$. A matching saturating $A$ exists if and only if $|N(S)| \ge |S| \quad \text{for every } S \subseteq A.$

The condition is plainly necessary; the converse carries the content: crowding is the only way a saturating matching can fail. Whenever no saturating matching exists, some set $S \subseteq A$ has fewer than $|S|$ neighbours between its members, and exhibiting that one set proves the failure.

Ways to work on it

• Walkthrough. Hall's condition for matching every vertex, and why it is necessary.
• Practice. Spot the set that violates Hall's condition.
• Hardest. Find the exact maximum matching size of a bipartite graph.

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