= Solution
Apply part (c) to the pairs $(X_1,X_2)$ and $(X_1,X_3)$. Outside a union of at most $2\epsilon 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>\epsilon$. Hence
$$
e(Y,Z)\geq(d-\epsilon)|Y||Z|\geq\frac d2\left(\frac{dn}2\right)^2=\frac{d^3n^2}8.
$$
Every such edge completes a distinct triangle through $v$. Thus at most $2\epsilon 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\leq1$ and $\epsilon<d/4\leq1/4$,
$$
\#\{\text{triangles in }G\}\geq(1-2\epsilon)n\frac{d^3n^2}8
\geq\boxed{\frac{d^3n^3}{16}}.
$$
Back to article page
