\documentstyle[a4,12pt]{article}
\newcommand{\Ff}{{\bf F}}
\newcommand{\Rr}{{\bf R}}
\newcommand{\eps}{\epsilon}
\newcommand{\lam}{\lambda}
\newcommand{\mod}{{\rm mod ~}}
\newcommand{\rk}{{\rm rk}}
\newcommand{\tr}{{\rm tr}}
\newcommand{\im}{{\rm im\,}}
\newcommand{\adj}{\,\sim\,}
\newcommand{\nadj}{\,\not\sim\,}

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\Remark}{ \noindent{\bf Remark:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}

\title{Toughness and spectrum of a graph}
\author{A.E. Brouwer}
\date{Oct. 7, 1993}
\begin{document}
\maketitle

\centerline{Dedicated to J.J. Seidel on the occasion of his 75th birthday.}

\medskip

\begin{abstract}
We derive (asymptotically best possible) lower bounds for
the toughness of a graph in terms of its eigenvalues.
\end{abstract}

The {\em toughness} of a finite connected graph $\Gamma$ with vertex set
$X$ is defined as the minimum of the quotient $|Z| / c(X \setminus Z)$ over
all subsets $Z$ of $X$ such that $c(X \setminus Z) > 1$, where $c(A)$ denotes
the number of connected components of the graph induced on $A$ by $\Gamma$.
For example, the toughness of the Petersen graph equals $4/3$, and the
unique way to achieve this quotient is by taking for $Z$ a 4-coclique
(and then $X \setminus Z$ carries the structure of $3K_2$).

Alon \cite{A} showed how to derive lower bounds for the toughness $t$
of a graph $\Gamma$ given its spectrum, and independently but later I
found similar results. However, by combining the two approaches it is
possible to prove the best possible result (up to an additive constant).

\begin{Theorem}
Let $\Gamma$ be a connected noncomplete regular graph of valency $d$ and
let $\lambda$ be the maximum of the absolute values of the eigenvalues
of $\Gamma$ distinct from $d$. Then the toughness $t$ of $\Gamma$
satisfies $t > d/\lam - 2$.
\end{Theorem}

The constant 2 can be improved a little, but not much, since there
are infinitely many examples of graphs with $t \le d/\lam$.
Indeed, for strongly regular graphs with smallest eigenvalue $s$
the Delsarte upper bound for the size of a coclique is
$|C| \le |X|/(1+d/(-s))$. When equality holds, we can take $Z = X \setminus C$
and find $t \le d/(-s)$. Now there are many cases where this upper
bound for the size of a coclique is met with equality; for example,
if we take for $\Gamma$ the complement of the collinearity graph
of a generalized quadrangle $GQ(q,q)$ ($q$ a prime power), then
the three distinct eigenvalues are $d = q^3$, $r = q$, and $s = -q$
so that $\lam = q$, and we find $q^2 - 2 < t \le q^2$.
The example of the Petersen graph above shows that $t$ can be
actually less than $d/\lam$ (it has $d = 3$ and $\lam = 2$).

\section{Interlacing lemma's}

We use interlacing in two forms: (i) The eigenvalues of a subgraph
(all our subgraphs are induced) of $\Gamma$ interlace those of $\Gamma$,
and (ii) Given a partition $\Pi$ of the index set of a matrix $A$, define
a matrix $B$ by: $B_{R,S}$ equals the average row sum of the block of $A$
with rows indexed by $R$ and columns by $S$ (where $R,S \in \Pi$).
Then the eigenvalues of $B$ interlace those of $A$.
(These results are well-known - see e.g., \cite{CDS} or \cite{Haem,Haem1} or
\cite{BCN}. More can be said in case of equality.)

Applying (ii) to the adjacency matrix $A$ of $\Gamma$,
with the trivial partition having one part only, we find the very well-known

\begin{Lemma}
\label{nul}
The average valency of a graph is not more than its largest eigenvalue.
\end{Lemma}

(Applying it to $A^2$ we get the slightly better: The average squared
valency of a graph is not more than the square of its largest eigenvalue.)

Now assume that $\Gamma$ has eigenvalues $\theta_1 \ge \theta_2 \ge ... \ge \theta_n$.
Then by (i) the eigenvalues of the subgraph $\Delta$ induced on a subset $Y$
interlace those of $\Gamma$. In particular we find from the above lemma that
at most one component of $\Delta$ has average valency larger than $\theta_2$.

Next, let us apply (ii) to a matrix $M$ of order $n$ with constant row 
and column sums $k$,
with a partition $\Pi = \{R,S\}$ into two parts of sizes $r,n-r$,
and let the $(R,R)$-block of $M$ have average row sum $a$.
The $2 \times 2$ matrix $B$ now has eigenvalues $k$ and $(na - rk)/(n-r)$,
so that the latter value lies between the smallest and the second largest
eigenvalue of $M$. In particular we find, taking $M = A$ and $M = A^2$:

\begin{Lemma}
\label{een}
Let $\Gamma$ be regular of degree $d$ on $n$ vertices, and let the graph
induced on the $r$-set $R$ have average valency $e$. Then
$\theta_2 \ge (ne - rd)/(n-r) \ge \theta_n$, and hence
$r \le n(e - \theta_n)/(d - \theta_n)$.
\end{Lemma}

\begin{Lemma}
\label{twee}
Let $\Gamma$ be regular of degree $d$ on $n$ vertices, and put
$\lam =  \max (|\theta_2|, |\theta_n|)$. Then
$\sum_x (|\Gamma(x) \cap R|)^2 - d^2 r^2 / n \le \lam^2 r(n-r)/n$.
\end{Lemma}

(Indeed, the sum of all entries of the matrix $A^2$ in the $(R,R)$-block
equals the number of paths $\gamma \adj \xi \adj \delta$, with
$\gamma , \delta \in R$ and $\xi \in X$, that is, $\sum_x (|\Gamma(x) \cap R|)^2$.)

This last inequality can also be written as
$$ \sum_x \left(|\Gamma(x) \cap R| - {rd \over n} \right)^2 \le
{r(n-r) \over n} \lam^2.$$

\section{Proof of the theorem}
Let the graph $\Gamma$ have toughness $t$, and let $Z$ be a subset of
the vertex set $X$ such that $|Z| = t c$, where $c > 1$ is the number
of connected components of the graph induced on $Y := X \setminus Z$.
By Lemma \ref{een} (applied to a coclique obtained by choosing
one point from each component of $Y$), we have $c \le \lam n/(d+\lam)$.
As we saw in the previous section, at most one component of $Y$, $B$ say, has
average valency more than $\lam$; put $B := \emptyset$ if there is no such
component. Put $C := Y \setminus B$.
If $|Y| \le \lam n/d$, then $|Z| \ge (d-\lam)n/d$ so that
$t \ge (d^2 - \lam^2)/(d\lam) \ge d/\lam - 1$.
So we may assume that $|Y| > \lam n/d$. By Lemma \ref{twee} applied to $Y$
we find
\begin{equation}
|C|.\left({d|Y| \over n} - \lam \right)^2 \le
\sum_{x \in C} \left( |\Gamma(x) \cap Y| - {d|Y| \over n} \right)^2 \le
\lam^2 |Y|(1 - {|Y| \over n}).
\label{et}
\end{equation}
Put $\tau := |Y|/n = 1 - tc/n$. Then (\ref{et}) becomes
$$|C|.\left(\tau - {\lam \over d}\right)^2 \le {\lam^2 \over d^2} \tau tc ,$$
where $\lam/d < \tau < 1$. Thus,
\begin{equation}
t \ge {|C| \over \tau c} \left({d \over \lam} \tau -1 \right)^2 .
\label{to}
\end{equation}
We may assume that $\lam/d < 1/2$, otherwise there is nothing to prove.

Assume $|C| \ge c$ and $t \le d/\lam - 2$.
Then, using $c \le \lambda n / (d + \lambda)$, we have
$\tau = 1 - ct/n \ge 3\lam/(d+\lam) > \lam/d$.
Also, by (2), $t \ge (d\tau/\lambda - 1)^2 / \tau$.
Since the function $f(x) = d^2 x/\lambda^2 + 1/x$ is increasing
for $x \ge \lambda/d$, we find
$d/\lam - 2 \ge t \ge d^2\tau/\lam^2 + 1/\tau - 2d/\lambda \ge
3d^2 / (\lambda(d+\lam)) + (d+\lam)/3\lam - 2d/\lambda =
(4d^2 - 4d\lambda + \lambda^2)/(3\lambda(d+\lam)) >
(3d^2 - 3d\lambda - 6\lambda^2)/(3\lambda(d+\lam)) = d/\lam - 2$,
a contradiction.

That leaves us with the case $|C| = c-1$, $B$ is nonempty and
all components of $C$ are singletons. Now we have, instead of (\ref{et}),
the sharper
\begin{equation}
|C|.\left({d|Y| \over n} \right)^2 \le
\lam^2 |Y|(1 - {|Y| \over n}),
\label{tre}
\end{equation}
i.e.,
$$t \ge \tau (1 - {1 \over c}){d^2 \over \lam^2} \ge
\tau {d^2 \over 2\lam^2}.$$
If $\tau < 2\lam/(d+\lam)$, then $tc/n > (d-\lam)/(d+\lam)$, and since
$c/n \le \lam/(d+\lam)$ it follows that $t > d/\lam - 1$.
Thus, we may assume that $\tau \ge 2\lam/(d+\lam)$.
But then $t \ge d^2/\lam(d+\lam) > (d-\lam)/\lam = d/\lam - 1$.
\qed

\section{Remarks}
The above estimates may be improved by noticing that either
$|C|/c$ is much larger than $1$, or the average valency of $C$
is much less than $\lam$.
(But the computations become messy, and I have not pursued this.)

[For example, assume that $C$ has average valency $\gamma\lam$, where
$0 \le \gamma \le 1/2$. Instead of (\ref{to}) we now find
$$t \ge {|C| \over \tau c} \left({d \over \lam} \tau - \gamma \right)^2 .$$
If we want to prove $t > d/\lam - 1$, then we may assume
as above that $\tau \ge 2\lam/(d+\lam)$ and $|C| \ge c$, so
$$t \ge {d+\lam \over 2\lam} \left( {2d \over d+\lam} - {1 \over 2}
\right)^2 ,$$ i.e.,
$$t - ({d \over \lam} - 1) \ge
{2\lam \over d+\lam} + {d+\lam \over 8\lam} - 1 \ge 0 .$$
But one can check that it is impossible that equality holds in
all estimates, so if $C$ has average valency at most $\lam/2$
then indeed $t > d/\lam - 1$.]

On the other hand, since $d \ge \lam$ and $t$ can be arbitrarily
close to zero, in a result of the form $t \ge d/\lam - a$ for some
constant $a$ we must have $a \ge 1$ if the result holds for
arbitrary regular graphs.
(By the way, regularity is not very essential in the theorem -
similar results hold for arbitrary graphs.)
Stronger results can also be obtained by keeping $\theta_2$
and $\theta_n$ separate, instead of lumping them together in $\lam$.


\section{Acknowledgements}
This note would never have been written had I not read the last chapter
of Jan van den Heuvel's thesis \cite{Heuv} (which describes the contents
of a paper by Bauer, van den Heuvel and Schmeichel, where triangle-free $t$-tough
graphs are constructed for arbitrarily large $t$, thus destroying a
conjecture by Chv\'atal). I am also indebted to Jan van den Heuvel
for providing me with a copy of \cite{A}.
Willem Haemers taught me interlacing, and made several useful remarks
regarding the presentation here. Also the referee suggested some
improvements in the presentation.

\begin{thebibliography}{}

\bibitem[A]{A} Noga Alon,
{\it Tough Ramsey graphs without short cycles\/},
preprint, 1993.

\bibitem[BCN]{BCN} A.E. Brouwer, A.M. Cohen \& A. Neumaier,
{\it Distance-regular graphs\/}, Springer, Heidelberg, 1989.

\bibitem[CDS]{CDS} D.M. Cvetkovi\'c, M. Doob \& H. Sachs,
{\it Spectra of graphs\/}, V.E.B. Deutscher Verlag der Wissenschaften,
Berlin, 1979 and Academic Press, New York, 1980.

\bibitem[H0]{Haem} W.H. Haemers,
{\it Eigenvalue techniques in design and graph theory\/},
Reidel, Dordrecht, 1980. [= Thesis (T.H. Eindhoven, 1979);
 = Math. Centr. Tract 121 (Amsterdam, 1980)]

\bibitem[H1]{Haem1} W.H. Haemers,
{\it Interlacing eigenvalues and graphs\/},
this issue.

\bibitem[vdH]{Heuv} J. van den Heuvel,
{\it Degree and toughness conditions for cycles in graphs},
Ph.D. Thesis, Twente Univ., 1993.

\end{thebibliography}

\end{document}
