Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 17J / a

A matching from $X$ to $Y$ consists of disjoint edges saturating every vertex of $X$. The criterion is Hall marriage theorem.

For sufficiency, induct on $|X|$. If a nonempty proper $S\subset X$ is tight, $|N(S)|=|S|$, apply induction to $S,N(S)$ and to the graph left after deleting them. If no proper set is tight, choose any edge $xy$, delete its endpoints, and Hall still holds because every nonempty proper subset formerly had at least one spare neighbour. Induction completes the matching. Necessity is immediate.