n$-regular graph on $2n$ vertices. Denote by $(x, y)$ the concatenation of two $n$-dimensional vectors, $x$, $y$, into a $2n$ dimensional vector. Let $v$ be an eigenvector of $M$ corresponding to eigenvalue $\lambda$. It is easy to see that $v$ is also an eigenvalue of $\bar{M}$: If $v = \vec{1}$ (and thus $\lambda = d$) it corresponds to eigenvalue $n - \lambda$, otherwise to $(-\lambda)$.\
Thus, $(v, v)$ and $(v, -v)$ are both eigenvectors of $N$. If $v = \vec{1}$ they correspond to eigenvalues $n$, $2d-n$, respectively, otherwise to $0$, $2\lambda$. Since the $v$’s are linearly independent, so are the $2n$ vectors of the form $(v, v)$ and $(v, -v)$: Consider a linear combination of these vectors that gives $0$. Both the sum and the difference of the coefficients of each pair have to be $0$, and thus both are 0. So we know the entire spectrum of $N$, and see, since $d \leq \frac n 2$, that theorem \[main1\] holds for it.\
Let $H'$ be a complete bipartite graph that is close to $H$. Since $H$ differs from $H'$ by $o(n^2)$ edges, the same holds for subgraphs over the same set of vertices. In particular, $G$ is close to the subgraph of $H'$ spanned by the first $n$ vertices. Obviously, every such subgraph is itself complete bipartite.

\[no-graphs\] For every $0 < \delta < {\frac 1 2}$ and $c$, there are only finitely many $\delta n$-regular graphs with $\lambda_2 < c$.

Consider such a graph with $n$ large. By the previous corollary it is close to complete bipartite. Since it is also regular, it must be close to $K_{\frac n 2, \frac n 2}$, which contradicts the constraint $\delta < {\frac 1 2}$.

Graphs with both $\lambda_2$ and $\lambda_{n-1}$ bounded by a constant
----------------------------------------------------------------------

Theorem \[main1\] can loosely be stated as follows: A regular graph with spectrum similar to that of a bipartite graph ($\lambda_1$ being close to $n/2$ and $\lambda_2$ being close to $0$) is close to being complete bipartite. We conclude this section by noting that if we streng