= Solution
Let $B\subseteq X$ be the <vertices> with fewer than $(d/2)|Y|$ <neighbours> in $Y$. If $|B|\geq\varepsilon|X|$, regularity applies to the pair $(B,Y)$ and gives
$$
d(B,Y)\geq d(X,Y)-\varepsilon\geq d-\varepsilon\geq d/2.
$$
But averaging the defining strict degree <inequality> over $B$ gives $d(B,Y)<d/2$, a contradiction. Therefore
$$
\boxed{|B|<\varepsilon|X|.}
$$
Regularity controls the <neighbourhood> of almost every <vertex> because a large <set> of exceptional low-degree <vertices> would itself witness an irregular density.
Back to article page
