TheoremProved

Hall's marriage theorem

Statement

Let $G=(X \cup Y, E)$ be a finite bipartite graph. There exists a matching that saturates every vertex of $X$ if and only if for every subset $W \subseteq X$ , the neighborhood $N(W) \subseteq Y$ satisfies $|N(W)| \ge |W|$ .

Why is it true?

If any group of applicants $W$ collectively qualifies for fewer than $|W|$ jobs, then obviously they cannot all be hired into distinct jobs. Hall's theorem says this obvious necessary condition — checked across every subset $W$ — is actually the only obstacle: if no subgroup is bottlenecked, a full matching always exists.

Proof sketch

Necessity is immediate since a matching saturating $X$ maps each $W \subseteq X$ injectively into $N(W)$ . For sufficiency, use induction on $|X|$ : if $|N(W)| \ge |W|+1$ for every proper nonempty $W \subset X$ , match any $x \in X$ to any $y \in N(\{x\})$ and apply induction to $G - \{x,y\}$ , where Hall's condition still holds; otherwise some proper nonempty $W$ is tight ( $|N(W)| = |W|$ ), so match $W$ to $N(W)$ by induction and verify that $X \setminus W$ satisfies Hall's condition in $G - (W \cup N(W))$ , allowing the remaining vertices to be matched by induction as well.

Topics that use this theorem

Graphs, degree, and paths

Related theorems

Handshaking lemma

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Philip Hall (1935). On Representatives of Subsets