. Next add all possible $o(n^2)$ new edges between pairs of sets that have “good” edges between them. As $R$ is close to complete bipartite, we need to delete or add all edges between $o(k^2)$ pairs. Each such step modifies $l^2$ edges, altogether $o(l^2k^2) = o(n^2)$ modifications. Finally, divide the $o(n)$ vertices of the exceptional set evenly between the two sides of the bipartite graph, and add all the required edges, and the tally remains $o(n^2)$.

In essence, the proof shows that a graph with no dense induced subgraphs is close to complete bipartite. This claim is similar in flavor to Bruce Reed’s [*Mangoes and Blueberries*]{} theorem [@Reed99]. Namely, that if every induced subgraph $G'$ of $G$ has an independent set of size ${\frac 1 2}|G'| - O(1)$, then $G$ is close to being bipartite. The conclusion in Reed’s theorem is stronger in that only a [*linear*]{} number of edges need to be deleted to get a bipartite graph.

In fact, the proof gives something a bit stronger. Let $t_r(n)$ be the number of edges in an $n$-vertex complete $r$-partite graph, with parts of equal size. Using the general Stability Theorem ([@Sim]) instead of Lemma \[close-bi\], the same proof shows that if a graph has $t_n - o(n^2)$ edges and no dense induced subgraphs, then it is close to being complete $r$-partite.

$\delta n$-regular graphs
-------------------------

In Theorem \[main1\] we required that the degree is $n/2$. We can deduce from the theorem that this requirement can be relaxed:

Let $\G$ be a family of $d$-regular graphs, with $d \leq \frac n 2$, ($n$ being the number of vertices in the graph) and bounded second eigenvalue, then every $G \in \G$ is close to a complete bipartite graph.

Let $M \in \M_n$ be the adjacency matrix of such a $d$-regular graph, and denote $\bar{M} = J - M$, where $J$ is the all ones matrix. Consider the graph $H$ corresponding to the following matrix: $$\begin{aligned}
N =
\left(
\begin{array}{cc}
M & \bar{M} \\
\bar{M}^t & M
\end{array}
\right)\end{aligned}$$ Clearly $H$ is an $