es in $V\backslash (\Gamma_i \cup \Gamma_j)$ we obtain a bipartite graph. We have deleted only $o(n^2)$ edges, so the remaining graph still has $n^2/4 - o(n^2)$ edges. But this means that $|\Gamma_i|, |\Gamma_j| = \frac n 2 - o(n)$, and that the degree of each vertex in these sets is $\frac n 2 \pm o(n)$

Recall that the Regularity Lemma states that for every $\epsilon > 0$ and $m \in \N$ there’s an $M$, such that the vertex set of every large enough graph can be partitioned into $k$ subsets, for some $m \leq k \leq M$ with the following properties: All subsets except one, the “exceptional” subset, are of the same size. The exceptional subset contains less than an $\epsilon$-fraction of the vertices. All but an $\epsilon$-fraction of the pairs of subsets are $\epsilon$-regular.\
The regularity graph with respect to such a partition and a threshold $d$, has the $k$ subsets as vertices. Two subsets, $U_1$ and $U_2$ are adjacent, if they are $\epsilon$-regular, and $e(U_1,U_2) > dn^2$.

\[[@Diestal], Lemma 7.3.2\] Let $G$ be a graph on $n$ vertices, $d \in (0,1]$, $\epsilon = d^{-4}$. Let $R$ be an $\epsilon$-regularity graph of $G$, with (non exceptional) sets of size at least $\frac s {\epsilon}$, and threshold $d$. If $R$ contains a triangle, then $G$ contains a complete tripartite subgraph, with each side of size $s$.

If $G \in \G$, and $R$ is as in the lemma, with $s = 10 \lambda_2$, then $R$ is triangle free. In this case, if $R$ has $\frac {k^2} 4 - o(k^2)$ edges, then $R$ is close to complete bipartite.

If $R$ contains a triangle, then $G$ contains a complete tripartite subgraph, with $s$ vertices on each side. Let $U$ be the set vertices in this subgraph. Then $e(U) = 3s^2 = 300 \lambda_2^2$, but by lemma \[no-clique\] $e(U) \leq 50 \lambda_2^2$ - a contradiction. The second part now follows from Lemma \[close-bi\].

(Theorem) We would like to apply the Regularity Lemma to graphs in $\G$, and have $\epsilon = o(1)$, and $k = \omega(1)$ as well as $k = o(n)$. Indeed, this can be done. Since $M$ depen