Past exam of the Probability, statistics and options II course of the University of Oxford / 2009 / R / R2 / i / Solution

Use the equivalent bipartite formulation: the left set has $m$ vertices and a matching must cover it. Necessity is immediate, since distinct matched partners for any left subset must all lie in its neighborhood.

For sufficiency, induct on $m$. The cases zero and one are immediate from the neighborhood condition. If a nonempty proper left subset $A$ satisfies $|N(A)|=|A|$, induction matches $A$ into $N(A)$. For the remaining left vertices and remaining right vertices, any subset $B$ has at least $|B|$ available neighbors: applying Hall's inequality to $A\cup B$ and removing the $|A|$ possible neighbors in $N(A)$ proves this. Induction supplies the second matching, and the two combine.

If no nonempty proper subset has equality, all such subsets have at least one extra neighbor. Choose any left vertex and one of its neighbors and match them. After deleting the pair, each nonempty subset of the remaining left side originally was proper and had at least $|B|+1$ neighbors; losing the chosen right vertex leaves at least $|B|$. Induction completes the matching. Thusis sufficient as well as necessary. If the right set is infinite, any subset with infinitely many neighbors automatically meets the finite inequalities, and the same finite-left induction applies.