= Solution
Retain $0<\epsilon<d/2$ from the preceding part. In $X_1$, at most $\epsilon n$ vertices have too few neighbours in $X_2$, and at most $\epsilon n$ have too few in $X_3$. Since $d\le1$, $2\epsilon<1$, so some $x\in X_1$ is good for both. Put $Y_2=N(x)\cap X_2$ and $Y_3=N(x)\cap X_3$. Their sizes are at least $dn/2>\epsilon n$. Regularity of $(X_2,X_3)$ therefore gives
$$
d(Y_2,Y_3)>d(X_2,X_3)-\epsilon\ge d-\epsilon>0.
$$
There is an edge joining a vertex of $Y_2$ to a vertex of $Y_3$. Its two endpoints and $x$ form \b[a triangle]. The nonempty equal classes ensure this counting argument also covers small integer sizes.
Back to article page
