 Solution

Fix the requested $\epsilon >0$ and choose much smaller constants $\eta ,\delta ,\rho >0$ in that order. Apply the Szemerédi regularity lemma with regularity parameter $\rho$ and a sufficiently large lower bound $m_0$ to a largest triangle-free subgraph $F\subseteq G$. Letbe the resulting equitable partition, and form the reduced graph of a regularity partition $R$ on $[m]$ by joining $i$ and $j$ when $(V_i,V_j)$ is $\rho$-uniform in $F$ and has $F$-density at least $\delta$.

Choose $\rho <\delta /2$. If $R$ contained a triangle, the triangle embedding lemma for regular pairs would give a triangle in $F$. Thus $R$ is triangle-free, and Turan theorem gives

Part (c), with error $\eta$, holds simultaneously for every pair of sets of size at least $n/\log n$. Since $m$ is bounded independently of $n$, all regularity classes and their halves satisfy this size condition for large $n$. It follows that every cross-pair contains at most $(p+\eta )|V_i||V_j|$ edges of $G$. It also givestake a bipartition of $V_i$ carrying at least half its internal edges and apply the cross-pair estimate.

Now count the edges of $F$. Pairs represented in $R$ contribute at mostThe exceptional set, the at most $\rho m^2$ irregular pairs, pairs of $F$-density below $\delta$, and edges inside classes together contribute at mostChoose $\eta$, then $\delta ,ho$, and finally $m_0^{-1}$ small enough in terms of $p\epsilon$. The total is at mostwith high probability, as required.