Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 4 / d / Solution

Let $S$ be the vertices of $X$ with fewer than $d|Y|/2$ neighbours in $Y$. If $|S|>ϵn$, it is a permissible subset in the regularity test, and averaging those degrees gives $d(S,Y)<d/2$. But $d(X,Y)\ge d$, socontradicting regularity. Therefore there are at most $ϵn$ such vertices. The same argument in fact rules out $|S|\ge ϵn$ when that threshold is integral and nonzero.