\documentclass[a4paper]{article}
\usepackage{latexsym}
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\eop}{$\Box$}
\newcommand{\qed}{\hfill\eop\medskip}
\newcommand{\adj}{\sim}
\newcommand{\nadj}{\not\sim}
\newcommand{\norm}{\|}

\begin{document}
\title{The vertex-connectivity of a distance-regular graph}
\author{Andries E. Brouwer \&
Jack H. Koolen\thanks{Supported by the Com$^2$MaC-SRC/ERC
program of MOST/KOSEF (grant $\sharp$ R11-1999-054).}}
\date{}
\maketitle
\begin{center}{\it To Eiichi Bannai, on the occasion of his 60th birthday}\end{center}
\begin{abstract}
The vertex-connectivity of a distance-regular graph
equals its valency.
\end{abstract}

\section{Introduction}
In this paper we prove the following theorem.

\medskip\noindent
{\bf Theorem}\quad{\it
Let $\Gamma$ be a non-complete distance-regular graph of valency $k > 2$.
Then the vertex connectivity $\kappa(\Gamma)$ equals $k$, and the only
disconnecting sets of vertices of size $k$ are the point neighbourhoods.
}

\medskip
The special case of this theorem where $\Gamma$ has diameter 2 was proved by
Brouwer \& Mesner \cite{BM} more than twenty years ago.
The case of diameter 3 was announced by the first author
at the conference celebrating Eiichi Bannai's 60th birthday.

\medskip
The upper bound $k$ is tight. For example,
an icosahedron (with $k = 5$) can be disconnected by removing a hexagon,
leaving two triangles, and the line graph of the Petersen graph
(with $k = 4$) can be disconnected by removing a 5-coclique,
leaving two pentagons.

\medskip
The edge connectivity of distance-regular graphs was determined earlier.

\begin{Proposition}\label{edgeconn}{\rm (Brouwer \& Haemers \cite{BH})}
Let $\Gamma$ be a distance-regular graph with more than one vertex.
Then its edge-connectivity equals its valency $k$, and the only disconnecting
sets of $k$ edges are the sets of edges incident with a single vertex.
\end{Proposition}

\section{Tools}

% \subsection{Expansion}
Given good information on the eigenvalues, expansion properties
follow from the below version of Tanner's bound.

\begin{Proposition}\label{separ}{\rm (Haemers \cite{IPM})}
Let $\Gamma$ be a regular graph of valency $k$ with second largest
eigenvalue $\theta$ and smallest eigenvalue $\theta'$.
Let $A$ and $B$ be two separated sets in $\Gamma$ of sizes
$a$ and $b$, respectively. Then
$${ab \over (v-a)(v-b)} \le ({\theta-\theta' \over 2k-\theta-\theta'})^2 .$$
\end{Proposition}

If the separating set $S$ has size $s$, so that $v-a = b+s$, then
an equivalent formulation is
${ab \over vs} \le { (\theta-\theta')^2 \over 4(k-\theta)(k-\theta') }$.

% \medskip
% \Proof
% Let $M$ be the adjacency matrix of $\Gamma$ and consider the
% matrix $N = \left(\begin{tabular}{cc}
% 0 & $xI-M$ \\
% $xI-M$ & 0 \\
% \end{tabular}\right)$.
% The eigenvalues of $N$ are $\pm(x-\xi)$, where
% $\xi$ runs through the eigenvalues of $M$.
% Consider the partitioning of the matrix $N$ induced by
% $A$, $S \cup B$, $A \cup S$, $B$ (in this order).
% By interlacing, the eigenvalues of the matrix of order 4 of
% average row sums interlace those of $N$.
% Choosing $x = \frac{1}{2}(\theta+\theta')$ we obtain the claimed result. \qed

% \subsection{Coding}
\medskip
For combinatorial work, the coding-theoretic argument below is useful.
We'll quote this as the `inproduct bound'.

\begin{Lemma}
Among a set of $a$ binary vectors of length $n$ and average weight $w$
there are two with inner product at least
$w({aw \over n} - 1)/(a-1) = {w^2 \over n} - {w(n-w) \over n(a-1)}$.
\end{Lemma}
\Proof
% (x+e)^2 + (x-e)^2 > 2x^2
The sum of all pairwise inner products of the vectors is at least
$n{aw/n \choose 2}$. \qed

% \subsection{The Shadow Lemma}
\medskip
\begin{Lemma}\label{shadow}
Let $\Gamma$ be a distance-regular graph with a separation
$\Gamma \setminus S = A + B$, and let $\alpha \in A$.
If $\alpha$ has $s$ neighbours in $S$, then
$|A| > v (1 - {s \over k})(1 - {k \over k_2})$.
\end{Lemma}
\Proof
According to Lemma 4.3(i) (the `Shadow Lemma') and subsequent remark
in Brouwer \& Haemers \cite{BH} one has
$|A| \ge v - \sum_i {s_i \over k_i}(k_i + \cdots + k_d)$
where $s_i = |S \cap \Gamma_i(\alpha)|$,
and $(k_i + \cdots + k_d)/k_i \ge (k_{i+1} + \cdots + k_d)/k_{i+1}$,
so that
$|A| \ge v - {s \over k}(v-1) - {k-s \over k_2}(v-1-k)
> v (1 - {s \over k})(1 - {k \over k_2})$.
\qed

\section{Vertex connectivity of a distance-regular graph}
Let us say that a distance-regular graph $\Gamma$ is OK when
its vertex connectivity equals its valency $k$, and the only
disconnecting sets of size $k$ are the sets of neighbours of a vertex.

Let $\Gamma$ be a distance-regular graph of diameter $d$ at least 3,
not a polygon, and suppose $S$ is a set of vertices of size
at most $k$ such that $\Gamma \setminus S$ is disconnected,
say with separation $A+B$. Suppose moreover that each of $A$ and $B$
contains at least two vertices. We shall obtain a contradiction.
Notation is as in BCN \cite{BCN}.

Put $a = |A|$, $b = |B|$, $s = |S|$.

\begin{Lemma}\label{nobiglb}
In any distance-regular graph of diameter more than $2$
one has $3\lambda+4 \le 2k$.
\end{Lemma}
\Proof
Suppose $\alpha \adj \beta \adj \gamma \adj \delta$ is a geodesic.
If $3\lambda+3 \ge 2k$, then $\lambda > 2(b_1-1)$, so that not
all common neighbours of $\beta$ and $\gamma$ are nonadjacent to $\alpha$
or nonadjacent to $\delta$. But then $\alpha$ and $\delta$ have a common
neighbour, contradiction. \qed

\begin{Lemma} Neither $A$ nor $B$ is a clique.
\end{Lemma}
\Proof
Suppose $A$ is a clique of size $a$. Apply the inproduct bound
to the $a$ vectors $\Gamma(\alpha) \cap S$ of length at most $k$
and weight $k-(a-1)$, and find
$\lambda \ge a-2 + {(k-a+1)(k-a) \over k}$.
The right hand side is minimal for $a = (k+1)/2$, and hence
$\lambda \ge \frac{3}{4}k - \frac{3}{2} - \frac{1}{4k}$.
On the other hand, by Lemma \ref{nobiglb},
$\lambda \le \frac{2}{3}k - \frac{4}{3}$
and hence $k = 3$, $\lambda = 0$, contradiction. \qed

\begin{Lemma}\label{agt3}
$a > 3$.
\end{Lemma}
\Proof
If $a = 3$, then $A$ is a path of length 2, and
$3+k \ge a+|S| \ge 3+3k-4-2\lambda-(\mu-1) = 3k-2\lambda-\mu$,
so that $2b_1 \le \mu+1 \le b_1$, impossible.
% (If $b_1 = \mu = 1$ then $\lambda = 0$ and $k = 2$.)
\qed

\begin{Lemma}\label{kgt3}
If $k = 3$ then $\Gamma$ is OK.
\end{Lemma}
\Proof
Suppose $k = 3$, and pick the separation $\Gamma \setminus S = A + B$
such that $S$ has minimal size (at most 3) and $A$ has minimal size
larger than one (so that $|B| \ge |A| > 3$), given the size of $S$.
If a point of $S$ has only one neighbour in $A$, then $A$ can be made
smaller. If a point of $S$ has no neighbours in $A$, then
$S$ can be made smaller. So, we may assume that each point of $S$
has precisely two neighbours in $A$ and one in $B$.
But then there is a disconnecting set of three edges,
not all on a single point, contradicting Proposition \ref{edgeconn}.
\qed

\begin{Lemma}\label{agt7}
If $\lambda = 0$ and $\mu = 1$ then $a > 7$.
\end{Lemma}
\Proof
Each point of $A$ has $k$ neighbours in $A \cup S$, and each
pair of nonadjacent vertices of $A$ have a common neighbour.
We may assume that $A$ is connected, and then it has at least $a-1$ edges.
We find $ak - {a \choose 2} + a-1 \le a+|S|$. Now use $k > 3$.
\qed

\begin{Lemma}\label{icosa}
The icosahedron is OK.
\end{Lemma}
\Proof This is a special case of the following lemma. \qed

\begin{Lemma}\label{antip}
An antipodal 2-cover of a complete graph is OK.
\end{Lemma}
\Proof
Let $\Gamma$ be an antipodal 2-cover of a complete graph $K_{k+1}$.
Since $|S| \le k$ there is a pair of antipodal vertices neither
of which is in $S$. If both are in $A$, then each vertex of $B$
is adjacent to some vertex of $A$, impossible. So, we have antipodal
$\alpha_0 \in A$ and $\beta_0 \in B$. Let $A' = A \setminus \{\alpha_0\}$
and let $B'$ be the set of antipodes of $B \setminus \{\beta_0\}$.
The graph $\Delta := \Gamma(\alpha_0)$ is strongly regular and
satisfies $k_{\Delta} = 2\mu_{\Delta}$ (BCN 1.5.3).
The sets $A'$ and $B'$ are subsets of $\Delta$ and $|A'|+|B'| \ge k$
and every vertex of $A'$ is equal or adjacent to every vertex of $B'$.
Now neither $A'$ nor $B'$ is a clique, so if $\alpha_1,\alpha_2$
are two nonadjacent vertices in $A'$ and $\beta_1,\beta_2$ two
nonadjacent vertices of $B'$, then $k_\Delta = 2\mu_\Delta =
\mu_\Delta(\alpha_1,\alpha_2)+\mu_\Delta(\beta_1,\beta_2) \ge
|B'|+|A'| \ge k = v_\Delta$,
impossible.
\qed

\begin{Lemma} $k_2 > k$.
\end{Lemma}
\Proof
One always has $\mu \le b_1$ and hence $k_2 \ge k$.
If equality holds then by BCN 5.1.1(v) $\Gamma$ has diameter 3
and is an antipodal 2-cover $(k_3 = 1)$, so is OK by Lemma \ref{antip}.
\qed

\begin{Lemma}\label{biglbmu}
$\max(\lambda+2,\mu) \ge k(k+1)/(a+k)$.
\end{Lemma}
\Proof
Apply the inproduct bound to the $a$ vectors
$\{\alpha\} \cup \Gamma(\alpha)$ for $\alpha \in A$,
of length $a+k$ and weight $k+1$, and find
$\max(\lambda+2,\mu) \ge k(k+1)/(a+k)$. 
\qed

\begin{Proposition}\label{largelbok}
If $\lambda > 0$ and $\mu > 1$ and $\lambda+2 \ge \mu$ then $\Gamma$ is OK.
\end{Proposition}
\Proof
By BCN 4.4.3 we have:
either $\Gamma$ is the icosahedron, or $\lambda = 0$, or $\mu = 1$,
or both $\theta_1 \le b_1 - 1$ and $-\theta_d \le \frac{1}{2}b_1+1$.
In the latter case the separation bound gives
$${ab \over (v-a)(v-b)} \le ({\frac{3}{2}b_1 \over 2k+2-\frac{1}{2}b_1})^2 .$$

Put $a = \alpha k$, $b_1 = \beta (k+1)$.
Since $\lambda+2 \ge {k(k+1) \over a+k} = \frac{1}{1+\alpha}(k+1)$,
we have $\beta \le \frac{\alpha}{1+\alpha}$.
Let $\gamma$ be the RHS of the separation bound.
Then $\gamma \le (\frac{3\beta}{4-\beta})^2 \le ({3\alpha \over 4+3\alpha})^2$
and $ab \le \gamma (v-a)(v-b) \le \gamma (a+k)(b+k)$.
On the left $b$ has coefficient $a$, on the right
the coefficient is $\gamma (a+k)$. Now $\gamma (\alpha+1) < \alpha$,
so assuming $b \ge a$ we may substitute $a$ for $b$ and obtain
$a^2 \le \gamma (a+k)^2$. But this is a contradiction. \qed

Now the proof is split into the three cases $\mu = 1$,
and $\lambda = 0$, $\mu > 1$, and $2 < \lambda + 2 < \mu$.
The first of these will be handled in Lemma \ref{munot1} below.
The second in Lemma \ref{lbnonzero}.

% \subsection{$\mu = 1$}
% In this subsection, we handle the case $\mu = 1$.
% (But that assumption will always be stated explicitly when used;
% some of the results here will be needed later as well.)

\medskip
Call a point in $A \cup B$ a {\em deep point} if it has no neighbours in $S$.

\begin{Lemma}\label{k2lt3k}
If $\lambda = 0$ and $k_2 \ge 3k$, then $\Gamma$ is OK.
\end{Lemma}
\Proof
Let $\sigma$, $\tau$ be the minimum number of neighbours some point of
$A$ resp. $B$ has in $S$. Then
$|A| > \frac{2}{3}v(1 - {\sigma \over k})$ and
$|B| > \frac{2}{3}v(1 - {\tau \over k})$ by Lemma \ref{shadow}.
Since $|A|+|B| < v$ we have $\sigma + \tau > \frac{1}{2}k$.
Since $\lambda = 0$ we have $\sigma,\tau \le \frac{1}{2}k$,
so $\sigma,\tau$ are nonzero, that is, neither $A$ nor $B$ has a deep point.

Put $a = |A|$ and $b = |B|$ and assume $a \le b$.
Count edges incident with vertices in $S$. One finds
$\sigma a + \tau b \le k^2$, so that $a < 2k$.
Since $\sigma,\tau \ge \mu$ we have $v \le k + {k^2 / \mu}$.
If $\mu > 1$ then by Lemma \ref{biglbmu}, $\mu > k^2/(a+k) > \frac{1}{3}k$,
so that $v < 4k$, contradiction.
If $\mu = 1$, then by the same lemma $a+k > k(k+1)/2$, but $a < 2k$
and hence $k \le 4$. By Lemma \ref{agt7} $a > 7$, contradiction.
\qed

\begin{Lemma}\label{k2lt4k}
If $k_2 \ge 4k$ and $v \ge 6k$, then $\Gamma$ is OK.
\end{Lemma}
\Proof
Let $\sigma$, $\tau$ be the minimum number of neighbours some point of
$A$ resp. $B$ has in $S$. Then
$|A| > \frac{3}{4}v(1 - {\sigma \over k})$ and
$|B| > \frac{3}{4}v(1 - {\tau \over k})$ by Lemma \ref{shadow}.
Since $|A|+|B| < v$ we have $\sigma + \tau > \frac{2}{3}k$.

If $\sigma > \frac{2}{3}k$ then $\lambda, \mu > \frac{1}{3}k$
and $k_2 < 2k$, contradiction.

So, $\sigma,\tau \le \frac{2}{3}k$ and $\sigma,\tau$ are nonzero,
that is, neither $A$ nor $B$ has a deep point.

Put $a = |A|$ and $b = |B|$ and assume $a \le b$.
Count edges incident with vertices in $S$. One finds
$\sigma a + \tau b \le k^2$, so that $a < \frac{3}{2}k$.
On the other hand,
$a > \frac{3}{4}v(1 - {\sigma \over k}) \ge \frac{1}{4}v \ge \frac{3}{2}k$,
contradiction.
\qed

\begin{Lemma}\label{munot1}
If $\mu = 1$, then $\Gamma$ is OK.
\end{Lemma}
\Proof
Since $\mu = 1$ we have lines of size $\lambda+2$,
and $(\lambda+1) | k$, hence $(\lambda+1) | b_1$.
Since $k_2 = b_1k$ we have $b_1 < 5$ by Lemma \ref{k2lt4k}.
This leaves the cases
$(k,\lambda) \in \{(3,0), (4,0), (5,0), (4,1), (6,1), (6,2), (8,3)\}$.
The cases with $\lambda = 0$ are settled by Lemmas \ref{kgt3} and \ref{k2lt3k}.
This leaves $(k,\lambda) \in \{(4,1), (6,1), (6,2), (8,3)\}$.

\medskip
(i) Suppose $(k,\lambda) = (4,1)$.
Now $\Gamma$ is the line graph of a cubic graph.
There are four arrays with $d \ge 3$
(see e.g. Brouwer \& Koolen \cite{BK})
namely
$\{4,2,1;1,1,4\}$ for the line graph of the Petersen graph on 15 vertices,
$\{4,2,2;1,1,2\}$ for the flag graph of the Fano plane on 21 vertices,
$\{4,2,2,2;1,1,1,2\}$ for the flag graph of $GQ(2,2)$ on 45 vertices,
and $\{4,2,2,2,2,2;1,1,1,1,1,2\}$ for the flag graph of $GH(2,2)$
on 189 vertices.

In these four cases the separation bound yields
$a \le 2$, $a \le 3$, $a \le 5$, $a \le 9$, respectively.
Since we have $k_2 = 2k = 8$, the shadow bound
(Lemma \ref{shadow}) yields $a > v/8$. Since also $a > 3$,
this settles the case $(k,\lambda) = (4,1)$.

\medskip
(ii) Suppose $(k,\lambda) = (6,1)$ or $(k,\lambda) = (6,2)$.
If $k=6$, $\lambda \in \{1,2\}$, $\mu = 1$, $k_2 \in \{24,18\}$,
then $\sigma + \tau > 3$ (because of $v$), so $\sigma + \tau \ge 4$.
Also $\sigma \le 3$ (because of $\mu$) so
and $A,B$ do not have deep points.
By the inner product bound (with $w = k = 6$ and $n = a+k$) we
have $a \ge 9$. On the other hand, $a \le k^2/(\sigma + \tau) \le 9$.
So $a = 9$ and $\sigma + \tau = 4$ and
$\sigma a + \tau b \le k^2$ and $a \le b$ imply $b = 9$.
Now $v \le a+b+k = 24$ and $v > 1+k+k_2 \ge 25$, contradiction.

\medskip
(iii) Suppose $(k,\lambda) = (8,3)$.
Then each point is in 2 cliques of size 5, and $\Gamma$ is the
line graph of a graph of valency 5. 
If $d \ge 4$ then $v > k + k_2 + (k_3 + k_4) > 6k$, and $\Gamma$ is OK
by Lemma \ref{k2lt4k}.
So, $d = 3$. Now by BCN 4.2.16, $\Gamma$ is the flag graph of $PG(2,4)$
on 105 vertices, and we are done again since $v > 6k$.
\qed


% \subsection{$\lambda = 0$ and $\mu > 1$}
% In this subsection, we handle the case $\lambda = 0$, $\mu > 1$.
% (But that assumption will always be stated explicitly when used;
% some of the results here will be needed later as well.)

\begin{Lemma}\label{muub}
If $d \ge 4$, or if $d = 3$ and $\Gamma$ is not bipartite,
then $\mu \le \frac{1}{2}k$.
\end{Lemma}
\Proof
If $d \ge 4$ this is trivial.
Suppose $d = 3$ and $\Gamma$ is not bipartite and $\mu > k/2$.
If $d(\alpha,\beta) = d(\beta,\gamma) = 2$ and $d(\alpha,\gamma) = 3$,
then $\beta$ has $\mu$ common neighbours with each of $\alpha,\gamma$,
and none occurs twice, so has more than $k$ neighbours. Contradiction.
Hence $p^3_{22} = 0$, and the graph $\Gamma_2$ is (connected and)
distance-regular with distances 0, 1, 2, 3 corresponding to
0, 2, 1, 3 in $\Gamma$. But then $k_2 \le k$, contradiction.
\qed

\begin{Lemma}\label{abig}
If $d \ge 4$, or $d = 3$ and $\Gamma$ is not bipartite,
and $\mu \ge \lambda+2$, then $a > k$.
\end{Lemma}
\Proof
If $a \le k$ then by Lemma \ref{biglbmu} $\max(\lambda+2,\mu) > \frac{1}{2}k$.
Now apply Lemma \ref{muub}.
\qed

\begin{Lemma}\label{onedeep}
Suppose $B$ has a deep point and $A$ does not.
If $\lambda+2 \le \mu$ then there is a separating set smaller than $S$.
\end{Lemma}
\Proof
Let $B'$ be the set of points in $B$ with a neighbour in $S$.
Put $s := |S|$ and $b' := |B'|$.
Each point in $A \cup B'$ has at least $\mu$ neighbours in $S$,
so $\mu(a+b') \le ks$. Since $a+k > {k^2 \over \mu}$ (by Lemma \ref{biglbmu})
it follows that $\mu(b'-s) < -(k-\mu)(k-s) \le 0$ so that $b' < s$.
Since $B$ has a deep point, $B'$ is a separating set.
\qed

\begin{Lemma}\label{lbnonzero}
If $\lambda = 0$ and $\mu > 1$ then $\Gamma$ is OK.
\end{Lemma}
\Proof
Suppose $\lambda = 0$ and $\mu > 1$.

By Lemma \ref{onedeep} either both or
neither of $A$ and $B$ have a deep point.

If $A$ and $B$ have deep points $\alpha$ and $\beta$, then
$|A|, |B| > v(1 - {\mu \over k-1})$, so that $2\mu > k-1$.
Now $d \ge d(\alpha,\beta) \ge 4$ and $\mu = k/2$ by Lemma \ref{muub}.
We have $d = 4$, otherwise $k/2 = \mu < c_3 \le b_2 \le k/2$
would give a contradiction. Now $|S| \ge k_2 > k$.

If neither $A$ nor $B$ has a deep point (and $S$ is minimal) then
every point of $A$ (or $B$) has distance 2 to some point
of $B$ (or $A$), and therefore has at least $\mu$ neighbours in $S$.
Counting edges meeting $S$ we find $v-k \le |A|+|B| \le k^2/\mu$.

Now $v \le k + {k^2 \over \mu}$ and $k_2 = {k(k-1) \over \mu}$
gives $1 + k_3 \le v - k - k_2 \le {k \over \mu}$ so that
$k_3 < {k-1 \over \mu}$ (because $\mu > 1$).
On the other hand, $c_3 \le k$ and $b_2 \ge 1$ imply
$k_3 = {k(k-1)b_2 \over \mu c_3} \ge {k-1 \over \mu}$, contradiction.
\qed

% \subsection{$\mu > \lambda + 2 > 2$}
% In this subsection, we handle the last case: $\mu > \lambda + 2 > 2$.
% As before, assumptions are always stated explicitly.

\begin{Lemma}\label{d3}
If $d \ge 4$ then $\Gamma$ is OK.
\end{Lemma}
\Proof
By Proposition \ref{largelbok} and Lemmas \ref{lbnonzero}, \ref{munot1}
we may assume $\lambda > 0$ and $\lambda+2 < \mu$.
By BCN Lemma 5.5.5 we have $a_2 \ge \mu$,
and since also $b_2 \ge \mu$ (since $d \ge 4$)
it follows that $\mu \le k/3$ and $b_1 > 2k/3$.

By Lemma \ref{onedeep} either both or
neither of $A$ and $B$ have a deep point.

If both $A$ and $B$ have a deep point, then
$v > |A| + |B| > 2v(1 - {\mu \over b_1}) > v$, contradiction.

If neither $A$ nor $B$ has a deep point, then
$1+k+{k(k-1-\lambda) \over \mu}+k+1 \le v \le k + {k^2 \over \mu}$,
again a contradiction.
\qed

\begin{Lemma}\label{th3big}
If $\lambda > 0$ then $\theta_d \ge -\frac{1}{2}b_1-1 \ge -\frac{1}{2}k$.
\end{Lemma}
\Proof
By BCN 4.4.3(iii), if $b_1 / (\theta_d + 1) > -2$, then
either $\lambda = 0$ or $\Gamma$ is the icosahedron,
but the icosahedron is OK by Lemma \ref{icosa}.
\qed

\begin{Proposition}\label{farconn}
Let $(u_i)$ be the standard sequence for the second largest eigenvalue
$\theta_1$. If $u_{d-1} > 0$ then $\theta_1 < a_d$, and
for each vertex $\alpha$ the subgraph $\Gamma_d(\alpha)$ is connected.
\end{Proposition}
\Proof
We have $c_d u_{d-1} + a_d u_d = \theta_1 u_d$, and $u_d < 0$
(since $(u_i)$ has precisely one sign change), so $\theta_1 < a_d$.
By interlacing $\Gamma_d(\alpha)$ has eigenvalue $a_d$ with multiplicity 1,
and hence is connected.
\qed

\begin{Proposition}\label{th1ad}
If $\lambda > 0$ and $\mu > 1$ and $\theta_1 < a_d$, then
$\Gamma$ is OK.
\end{Proposition}
\Proof
By Lemma \ref{th3big} we have $\theta_d \ge -\frac{1}{2}k$.
By Proposition \ref{largelbok} we may assume $\mu \ge \lambda+2$.

Put $a = \alpha k$. Then $c_d \ge \mu > \frac{k}{1+\alpha}$,
hence $a_d = k-c_d < \frac{\alpha k}{1+\alpha}$.
Using $\theta_1 < \frac{\alpha k}{1+\alpha}$ and $-\theta_d \le \frac{1}{2}k$
we find from the separation bound that
$${ab \over (v-a)(v-b)} \le ({3\alpha+1 \over 3\alpha+5})^2 .$$
Let $\gamma$ be the RHS of the separation bound.
Then $ab \le \gamma (v-a)(v-b) \le \gamma (a+k)(b+k)$.
On the left $b$ has coefficient $a$, on the right
the coefficient is $\gamma (a+k)$. Now $\gamma (\alpha+1) < \alpha$
(e.g.\ for $\alpha \ge 1$),
so assuming $b \ge a$ we may substitute $a$ for $b$ and obtain
$a^2 \le \gamma (a+k)^2$, so that $a \le k$,
contradicting Lemma \ref{abig}.
\qed

\begin{Lemma}\label{th1big}
Suppose $\lambda > 0$ and $\mu > 1$.
If $\theta_1 \le \frac{1}{2}k$, then $\Gamma$ is OK.
\end{Lemma}
\Proof
If $\theta_1 \le \frac{1}{2}k$, then we can use the bound for
separated sets again with $\theta \le \frac{1}{2}k$
and $\theta' \ge -\frac{1}{2}k$. We find
$${ab \over (v-a)(v-b)} \le {1 \over 4}$$
so that $3ab \le vk$, and if $a \le b$ then
$a \le b \le (a+k)k/(3a-k)$, so $(3a+k)(a-k) \le 0$, that is, $a \le k$.
Now we are done by Lemma \ref{abig} and Proposition \ref{largelbok}.
\qed

% \begin{Lemma}\label{alb}
% If $d \ge 4$, or if $d = 3$ and $\Gamma$ is not bipartite,
% then $a \ge \frac{1}{2}k+2$.
% \end{Lemma}
% \Proof
% Two nonadjacent points of $A$ have at least $2k-\mu$ distinct neighbours
% inside a set of size at most $k+a-2$. Now apply Lemma \ref{muub}.
% \qed

% In order to apply the separation bound, we need to
% bound $\theta_1$ away from $k$.
% 
% \begin{Lemma} Let $d = 3$. Then $\theta_1 < \frac{1}{2}\sqrt{3} k$.
% \end{Lemma}
% \Proof
% Consider the Euclidean representation corresponding to
% the second largest eigenvalue $\theta_1$,
% with inner products $u_i$ $(i=0,1,2,3)$
% corresponding to distance $i$, where $u_0 = 1$.
% The sequence $(u_i)$ has a single sign change, so $u_3 < 0$.
% Now $u_i = \cos \phi_i$ where $\phi_i$ is the angle made by the
% vectors representing vertices at distance $i$, and since
% $\phi_3 > \pi/2$ and $\phi_3 \le 3\phi_1$, we have $\phi_1 > \pi/6$,
% so that $u_1 < \frac{1}{2}\sqrt{3}$. But $u_1 = \theta_1/k$,
% so $\theta_1 < \frac{1}{2}\sqrt{3} k$.
% \qed

% \begin{Lemma}\label{mediuma}
% Let $d = 3$. Suppose that $\frac{1}{2}k \le a \le 1 + k_2 - \frac{1}{2}k$.
% Then $k \le 2\lambda + 1 + \mu$.
% \end{Lemma}
% \Proof
% For each $\alpha \in A$ there are at least $b-k_3$ vertices
% $\beta \in B \cap \Gamma_2(\alpha)$. The $\mu$ common neighbours
% of $\alpha$ and $\beta$ lie in $S$, and each vertex of $S$ is seen
% at most $\frac{1}{4}k^2$ times, so that $a(b-k_3)\mu \le \frac{1}{4}k^3$,
% hence $a(1+k_2-a)\mu \le \frac{1}{4}k^3$.
% 
% The left hand side is maximal for $a = \frac{1}{2}(1+k_2)$, and
% in the stated interval we find
% $\frac{1}{2}k(1+k_2-\frac{1}{2}k)\mu \le \frac{1}{4}k^3$, hence
% $\mu + kb_1 -\frac{1}{2}k\mu \le \frac{1}{2}k^2$, i.e.,
% $k(b_1-\frac{1}{2}k) \le \mu(\frac{1}{2}k - 1)$ so that
% $b_1-\frac{1}{2}k < \frac{1}{2}\mu$, i.e., $k < 2\lambda + 2 + \mu$.
% \qed

\begin{Lemma}\label{th1small}
% $\theta_1 < b_1-1$.
$\theta_1 \le b_1-1$.
\end{Lemma}
\Proof
By BCN 4.4.3(ii) either $\theta_1 \le b_1 - 1$ or $\mu = 1$
or $\Gamma$ is the icosahedron. But $\mu > 1$ by Lemma \ref{munot1},
and $\Gamma$ is not the icosahedron by Lemma \ref{icosa}.
\qed

\begin{Lemma}\label{th1ok}
Let $d = 3$.
If $\frac{1}{2}k < \theta_1 \le b_1-1$ then $\theta_1 < a_3$.
\end{Lemma}
\Proof
Firstly, $\theta_1 > \frac{1}{2}k$ is equivalent to $u_1 > \frac{1}{2}$.
Secondly, $\theta_1 \le b_1-1$ is equivalent to $u_0 -2u_1 + u_2 \ge 0$.
Since $u_0 = 1$ this implies that $u_2 \ge 2u_1 - u_0 > 0$.
Now $\theta_1 < a_3$ follows by Proposition \ref{farconn}.
\qed

\begin{Theorem} $\Gamma$ is OK.
\end{Theorem}
\Proof
The cases $\lambda = 0$ and $\mu = 1$ were done in
Lemmas \ref{lbnonzero}, \ref{munot1}.
By Lemma \ref{d3} we may assume $d = 3$.
% Now the case $\lambda+2 \ge \mu$ is handled in Proposition \ref{largelbok}.
By Lemmas \ref{th1big}, \ref{th1small}, \ref{th1ok}
we have $\theta_1 < a_3$ and now Proposition \ref{th1ad}
completes the proof. \qed

\begin{thebibliography}{9}

% \bibitem{BBS}
% N. L. Biggs, A. G. Boshier \& J. Shawe-Taylor,
% {\it Cubic distance-regular graphs},
% J. London Math. Soc. (2) {\bf 33} (1986) 385--394.

\bibitem{BCN}
A. E. Brouwer, A. M. Cohen \& A. Neumaier,
{\it Distance-Regular Graphs}, Springer, Heidelberg, 1989.

\bibitem{BH}
A. E. Brouwer \& W. H. Haemers,
{\it Eigenvalues and perfect matchings},
Linear Alg. Appl. {\bf 395} (2005) 155--162.

\bibitem{BK}
A. E. Brouwer \& J. H. Koolen,
{\it The distance-regular graphs of valency four},
J. Alg. Combin. {\bf 10} (1999) 5--24. 

\bibitem{BM}
A. E. Brouwer \& D. M. Mesner,
{\it The connectivity of strongly regular graphs},
Europ. J. Combin. {\bf 6} (1985) 215-216.

\bibitem{IPM}
W. H. Haemers,
{\it Interlacing eigenvalues and graphs},
Lin. Alg. Appl. {\bf 226--228} (1995) 593--616.
% Lecture Notes for a course at IPM, Teheran, 2006.

\end{thebibliography}

\section*{Addresses of the authors}
A. E. Brouwer,\\
{\small Department of Mathematics, Techn. Univ. Eindhoven,} \\
{\small P.O. Box 513, 5600~MB Eindhoven, The Netherlands} \\
{\tt aeb@cwi.nl}

\medskip\noindent
J. H. Koolen,\\
{\small Department of Mathematics, POSTECH,} \\
{\small Pohang, South Korea}\\
{\tt koolen@postech.ac.kr}

\end{document}

