Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 4 / 14I / Solution

A matching in a graph from $X$ to $Y$ is a collection of edges with disjoint endpoints covering every vertex of $X$; equivalently it chooses a distinct neighbour in $Y$ for each $x\in X$. For a finite bipartite graph, the Hall marriage theorem says this exists exactly when $|N(A)|\ge |A|$ for every $A\subseteq X$. Necessity follows by counting the distinct matched neighbours.

For sufficiency, induct on $|X|$. If a nonempty proper subset $A$ is tight, $|N(A)|=|A|$, Hall's condition holds on $(A,N(A))$. It also holds on $(X\setminus A,Y\setminus N(A))$: for $B\subseteq X\setminus A$, the original condition applied to $A\cup B$ gives $|N(B)\setminus N(A)|\ge |B|$. Induction provides two disjoint matching in a graph whose union covers $X$. If no nonempty proper subset is tight, choose an edge $xy$, possible by Hall's condition. Delete its endpoints. Each nonempty subset of $X\setminus \{x\}$ had at least one extra neighbour, so deleting $y$ leaves Hall's condition intact. Induction and then the edge $xy$ finish the proof. The single-vertex case is immediate.

For the degree condition, fix $A\subseteq X$ and double-count with weights:Every denominator is nonzero; the last inequality uses $d(y)\le d(x)$ along each edge. The Hall marriage theorem therefore proves the required matching exists. Finiteness, as in the usual course version of the theorem, is understood; the same proof covers a finite $X$ with arbitrary $Y$ and finite degrees.