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

Verify Hall's marriage theorem. Let $S\subseteq X$; the empty case is immediate. If $0<|S|\le ϵn$, any $x\in S$ has at least $ϵn$ neighbors in $Y$, so $|N(S)|\ge |S|$.

Next suppose $ϵn<|S|\le (1-ϵ)n$. If $|N(S)|<|S|$, then $T=Y\setminus N(S)$ has $|T|>n-|S|\ge ϵn$. There are no edges between $S$ and $T$, so $d(S,T)=0$. But the regularity assumption impliesa contradiction.

Finally, if $|S|>(1-ϵ)n$, then $|X\setminus S|<ϵn$. Every $y\in Y$ has at least $ϵn$ neighbors in $X$, so at least one of them lies in $S$. Thus $N(S)=Y$ and $|N(S)|=n\ge |S|$.

All possible sizes of $S$ are covered, even if the middle range is empty. Hall's condition holds, so there is a perfect matching between $X$ and $Y$. This is the perfect matching criterion for a regular pair with minimum degree.