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

Retain $0<ϵ<d/2$ from the preceding part. In $X_1$, at most $ϵn$ vertices have too few neighbours in $X_2$, and at most $ϵn$ have too few in $X_3$. Since $d\le 1$, $2ϵ<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>ϵn$. Regularity of $(X_2,X_3)$ therefore givesThere is an edge joining a vertex of $Y_2$ to a vertex of $Y_3$. Its two endpoints and $x$ form a triangle. The nonempty equal classes ensure this counting argument also covers small integer sizes.