= Solution
Apply part (b) to $(X_1,X_2)$ and $(X_1,X_3)$. Fewer than $2\varepsilon|X_1|$ <vertices> fail at least one of the degree bounds. For any remaining <vertex> $v$, put $N_2=N(v)\cap X_2$ and $N_3=N(v)\cap X_3$. Then
$$
|N_2|\geq\frac d2|X_2|\geq\varepsilon|X_2|,\qquad
|N_3|\geq\frac d2|X_3|\geq\varepsilon|X_3|.
$$
Regularity of $(X_2,X_3)$ gives $d(N_2,N_3)\geq d-\varepsilon\geq d/2$. Every <edge> between $N_2$ and $N_3$ makes a distinct <triangle in a graph>[triangle] containing $v$. Hence $v$ belongs to at least
$$
\frac d2|N_2||N_3|\geq\frac{d^3}8|X_2||X_3|
$$
such <triangle in a graph>[triangles]. This proves the asserted bound on exceptional <vertices>.
There are at least $(1-2\varepsilon)|X_1|\geq|X_1|/2$ good <vertices>. Summing their <triangle in a graph>[triangle] counts counts each <triangle in a graph>[triangle] with one <vertex> in each cluster exactly once, at its $X_1$ <vertex>. Therefore
$$
\boxed{\#\{\text{triangles in }G\}\geq\frac{d^3}{16}|X_1||X_2||X_3|.}
$$
There is no factor of three to divide out in this cross-cluster count.
This is the <regular triangle counting lemma> with explicit coarse constants.
Back to article page
