Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / A / 3 / a

Hall's marriage theorem states that a finite bipartite graph with vertex classes $X,Y$ has a matching covering $X$ if and only ifNecessity follows because the matched neighbors of the vertices in $S$ are distinct members of $N(S)$.

For sufficiency, induct on $|X|$. The empty case is immediate. First suppose there is a nonempty proper subset $S\subset X$ with $|N(S)|=|S|$. The induced graph between $S$ and $N(S)$ satisfies Hall's condition, so induction matches $S$. In the remaining graph between $X\setminus S$ and $Y\setminus N(S)$, every $T\subseteq X\setminus S$ satisfiesInduction matches the rest, and the two matchings are disjoint.

Otherwise every nonempty proper $S\subset X$ has $|N(S)|\ge |S|+1$. Choose any edge $xy$, which exists by Hall's condition if $X$ is nonempty. Delete $x$ and $y$. Every nonempty subset of $X\setminus \{x\}$ loses at most one neighbor and therefore still satisfies Hall's condition. Induction provides a matching of this smaller graph; append $xy$. If $|X|=1$, choosing its neighbor already completes the argument. This proves the theorem.