y.\
In our search for further examples of graphs of linear sphericity, we investigate in section \[lambda2-cons\] families of graphs whose second eigenvalue is bounded by a constant (for which the aforementioned lower bound is linear). We show that such graphs are close to being complete bipartite, in the sense that one needs to modify only $o(n^2)$ entries in the adjacency matrix to get the latter from the former. As a corollary, we get that for $0 < \delta < {\frac 1 2}$, and $\lambda_2$ there are only finitely many $\delta n$-regular graphs with second eigenvalue at most $\lambda_2$.

 {#dope}

Definitions
-----------

Let $X = ([n],\delta)$ be a metric space on $n$ points, such that all pairwise distances are distinct. Let $||\;||$ be a norm on $\R^d$. We say that $\phi:X \rightarrow (\R^d,||\;||)$ is a [**]{} if for every $w,x,y,z \in X$, $\delta(x,y) < \delta(w,z) \Leftrightarrow ||\phi (x) - \phi (y)|| <
||\phi (w) - \phi (z)||$.

We denote by $d(X,||\;||)$ the minimal $t$ such that there exists a from $X$ to $(\R^t,||\;||)$. We denote by $d(n,||\;||) = \max_X d(X,||\;||)$, the smallest dimension to which every $n$ point metric can be mapped monotonically.

The first thing to notice is that we are actually concerned only with the [*order*]{} among the distances between the points in the metric space, and not with the actual distances. Let $(X,\delta)$ be a finite metric space, and let $\rho$ be a linear order on $X \choose 2$. We say that $\rho$ and $(X,\delta)$ are [*consistent*]{} if for every $w,x,y,z \in X$, $\delta(x,y) < \delta(w,z) \Leftrightarrow (x,y) <_\rho (w,z)$.

We start with an easy, but useful observation.

\[dope-lemma\] Let $X$ be a finite set. For every strict order relation $\rho$ on $X \choose 2$, there exists a distance function $\delta$ on $X$, that is consistent with $\rho$.

Let $\{\epsilon_{ij}\}_{(i,j)\in {X \choose 2}}$ be small, non-negative numbers, ordered as per $\rho$. Define $\delta(i,j) = 1 + \epsilon_{ij}$. It is obvious that $\delta$ induces the desired order on the dis