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

Apply part (c) to the pairs $(X_1,X_2)$ and $(X_1,X_3)$. Outside a union of at most $2ϵn$ exceptional vertices, every $v\in X_1$ has sets $Y=N(v)\cap X_2$ and $Z=N(v)\cap X_3$ of size at least $dn/2$.

These sets are large enough for epsilon-uniformity of $(X_2,X_3)$, because $d/2>ϵ$. HenceEvery such edge completes a distinct triangle through $v$. Thus at most $2ϵn$ vertices of $X_1$ fail the claimed triangle count. Summing these triangles over the good vertices counts each triangle with one vertex in each class exactly once. Since $d\le 1$ and $ϵ<d/4\le 1/4$,