Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 1 / 17F / i / Solution

Hall's marriage theorem states that a finite bipartite graph with parts $A,B$ has a matching in a graph saturating $A$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq A$. Necessity follows because the matched neighbours of $S$ are distinct.

For sufficiency use induction on $|A|$. The empty case is immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, the induced graph on $S,N(S)$ satisfies Hall's condition and has a saturating matching in a graph by induction. The remaining graph on $A\setminus S,B\setminus N(S)$ also satisfies it: for $T\subseteq A\setminus S$,Apply induction again and unite the two matchings in a graph. If there is no such tight proper subset, every nonempty proper $S$ has $|N(S)|\ge |S|+1$. Choose a vertex $a$ and a neighbour $b$, which exists by Hall's condition. Delete both. Every remaining subset loses at most one neighbour and still satisfies Hall's condition. Induction supplies a matching in a graph of the remainder; add $ab$. For $|A|=1$ this last step directly proves the assertion.