= Solution
Verify <Hall's marriage theorem>. Let $S\subseteq X$; the empty case is immediate. If $0<|S|\leq\epsilon n$, any $x\in S$ has at least $\epsilon n$ neighbors in $Y$, so $|N(S)|\geq|S|$.
Next suppose $\epsilon n<|S|\leq(1-\epsilon)n$. If $|N(S)|<|S|$, then $T=Y\setminus N(S)$ has $|T|>n-|S|\geq\epsilon n$. There are no edges between $S$ and $T$, so $d(S,T)=0$. But the <regular pair of vertex sets>[regularity] assumption implies
$$
d(S,T)\geq d(X,Y)-\epsilon>0,
$$
a contradiction.
Finally, if $|S|>(1-\epsilon)n$, then $|X\setminus S|<\epsilon n$. Every $y\in Y$ has at least $\epsilon n$ neighbors in $X$, so at least one of them lies in $S$. Thus $N(S)=Y$ and $|N(S)|=n\geq|S|$.
All possible sizes of $S$ are covered, even if the middle range is empty. Hall's condition holds, so \b[there is a <perfect matching> between $X$ and $Y$]. This is the <perfect matching criterion for a regular pair with minimum degree>.
Back to article page
