\documentclass[a4paper]{article}
\usepackage{latexsym}

\newtheorem{Theorem}{Theorem}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Corollary}[Theorem]{Corollary}
\newcommand{\qed}{\hfill$\Box$\medskip}
\newcommand{\adj}{\sim}

\title{A lower bound for the Laplacian eigenvalues
of a graph---proof of a conjecture by Guo}
\author{A. E. Brouwer \& W. H. Haemers}
\date{2008-02-28}

\begin{document}
\maketitle

\abstract{\noindent
We show that if $\mu_j$ is the $j$-th largest Laplacian eigenvalue,
and $d_j$ is the $j$-th largest degree $(1 \le j \le n)$ of a connected graph
$\Gamma$ on $n$ vertices, then $\mu_j \ge d_j - j + 2$ $(1 \le j \le n-1)$.
This settles a conjecture due to Guo.}

\section{Introduction}
Let $\Gamma$ be a finite simple (undirected, without loops) graph
on $n$ vertices. Let $X = V\Gamma$ be the vertex set of $\Gamma$.
Write $x \adj y$ to denote that the vertices $x$ and $y$
are adjacent. Let $d_x$ be the degree (number of neighbors) of $x$.

The {\em adjacency matrix} $A$ of $\Gamma$ is the 0-1 matrix indexed by $X$
with $A_{xy} = 1$ when $x \adj y$ and $A_{xy} = 0$ otherwise.
The {\em Laplacian matrix} of $\Gamma$ is $L = D - A$,
where $D$ is the diagonal matrix given by $D_{xx} = d_x$,
so that $L$ has zero row and column sums.

The eigenvalues of $A$ are called {\em eigenvalues} of $\Gamma$.
The eigenvalues of $L$ are called {\em Laplacian eigenvalues} of $\Gamma$.
Since $A$ and $L$ are symmetric, these eigenvalues are real.
Since $L$ is positive semidefinite (indeed, for any vector $u$ indexed
by $X$ one has $u^\top L u = \sum (u_x - u_y)^2$ where the sum is over
all edges $xy$), it follows that the Laplacian eigenvalues are nonnegative.
Since $L$ has zero row sums, 0 is a Laplacian eigenvalue. In fact the
multiplicity of 0 as eigenvalue of $L$ equals the number of connected
components of $\Gamma$.

Let $\mu_1 \ge \mu_2 \ge \ldots \ge \mu_n = 0$ be the Laplacian eigenvalues.
Let $d_1 \ge d_2 \ge \ldots \ge d_n$ be the degrees, ordered nonincreasingly.
We will prove that $\mu_i \ge d_i - i + 2$ with basically one exception.

\section{Exception}
Suppose $\mu_m = 0 < d_m - m + 2$. Then $d_m \ge m-1$, and we find a
connected component with at least $m$ vertices, hence with at least
$m-1$ nonzero Laplacian eigenvalues. It follows that this component
has size precisely $m$, and hence $d_1 = \ldots = d_m = m-1$, and the
component is $K_m$. Now $\Gamma = K_m + (n-m)K_1$ is the disjoint union
of a complete graph on $m$ vertices and $n-m$ isolated points.
We'll see that this is the only exception.

\section{Interlacing}
Suppose $M$ and $N$ are real symmetric matrices of order $m$ and $n$
with eigenvalues $\lambda_1(M)\geq\ldots\geq\lambda_m(M)$
and $\lambda_1(N)\geq\ldots\geq\lambda_n(N)$, respectively.
If $M$ is a principal submatrix of $N$, then it is well known
that the eigenvalues of $M$ interlace those of $N$, that is,
\[ \lambda_i(N)\geq\lambda_i(M)\geq\lambda_{n-m+i}(N)\ \mbox{ for }
\ i=1,\ldots,m \, .\]
Less well-known, (see for example~\cite{Haemers95}) is that these
inequalities also hold if $M$ is the quotient matrix of $N$
with respect to some partition $X_1,\ldots,X_m$ of $\{1,\ldots,n\}$.
This means that $(M_{i,j})$ equals the average row sum of the block
of $N$ with rows indexed by $X_i$ and columns indexed by $X_j$.

\medskip
Let $K$ be the point-line incidence matrix of a graph $\Gamma$.
Then the Laplacian of $\Gamma$ is $L = KK^\top$.
But $KK^\top$ has the same nonzero eigenvalues as $K^\top K$,
and interlacing for that latter matrix implies that the eigenvalues
of $L$ do not increase when an edge of $\Gamma$ is deleted.

\section{The lower bound}
\begin{Theorem}
Let $\Gamma$ be a finite simple graph on $n$ vertices,
with vertex degrees $d_1 \ge d_2 \ge \ldots \ge d_n$, and
Laplacian eigenvalues $\mu_1 \ge \mu_2 \ge \ldots \ge \mu_n$.
If $\Gamma$ is not $K_m + (n-m)K_1$, then $\mu_m \ge d_m - m + 2$.
\end{Theorem}

For the union of $K_m$ and some isolated points we have
$\mu_m = 0$ and $d_m = m-1$.

\medskip
The case $m = 1$ of this theorem ($\mu_1 \ge d_1+1$ if there is an edge)
is due to Grone \& Merris \cite{GroneMerris94}.
The case $m = 2$ ($\mu_2 \ge d_2$ if the number of edges is not 1)
is due to Li \& Pan \cite{LiPan00}.
The case $m = 3$ is due to Guo \cite{Guo07}, and he also conjectured
the general result.

\medskip
Let us separate out part of the proof as a lemma.

\begin{Lemma}
Let $S$ be a set of vertices in the graph $\Gamma$
such that each vertex in $S$ has at least $e$ neighbors outside $S$.
Let $m = |S|$, $m > 0$. Then $\mu_m \ge e$.
If $S$ contains a vertex adjacent to all other vertices of $S$,
and $e > 0$, then $\mu_m \ge e+1$.
\end{Lemma}

\noindent
{\bf Proof}
Consider the principal submatrix $L_S$ of $L$ with rows and columns
indexed by $S$. Let $L(S)$ be the Laplacian of
the subgraph induced on $S$. Then $L_S = L(S) + D$ where $D$ is
the diagonal matrix such that $D_{ss}$ is the number of neighbors
of $s$ outside $S$. Since $L(S)$ is positive semidefinite and
$D \ge eI$, all eigenvalues of $L_S$ are not smaller than $e$,
and by interlacing $\mu_m \ge e$.

\medskip
Now suppose that $S = \{s_0\} \cup T$, where $s_0$ is adjacent
to all vertices of $T$. Throw away all edges entirely outside $S$,
and possibly also some edges leaving $S$, so that each vertex of $S$
has precisely $e$ neighbours outside $S$. Also throw away all vertices
outside $S$ that now are isolated. Since these operations do not
increase $\mu_m$, it suffices to prove the claim for the resulting
situation.

Consider the quotient matrix $Q$ of $L$ for the partition of
the vertex set $X$ into the $m+1$ parts $\{s\}$ for $s \in S$
and $X \setminus S$.
% (That is, $Q_{AB}$ is the average row sum of the submatrix
% of $L$ with rows indexed by $A$, and columns by $B$.)
We find, with $r = |X \setminus S|$,
$$
Q = \left( \begin{array}{ccc}
e+m-1 & -1 \ldots -1 & -e \\
-1 &             & -e \\
\vdots &  L_T    & \vdots \\
-1 &             & -e \\
-e/r & -e/r \ldots -e/r & em/r \\
\end{array}\right) .
$$
Consider the quotient matrix $R$ of $L$ for the partition of
the vertex set $X$ into the 3 parts $\{s_0\}$, $T$, $X \setminus S$.
Then
$$
R = \left( \begin{array}{ccc}
e+m-1 & 1-m & -e \\
-1 & e+1 & -e \\
-e/r & -e(m-1)/r & em/r \\
\end{array}\right) .
$$
The eigenvalues of $R$ are 0, $e+m$, and $e + me/r$, and these three
numbers are also the eigenvalues of $Q$ for (right) eigenvectors that
are constant on the three sets $\{s_0\}$, $T$, $X \setminus S$.
The remaining eigenvalues $\theta$ of $Q$ belong to (left) eigenvectors
perpendicular to these, so of the form $(0,u^\top,0)$ with $\sum u = 0$.
Now $L_T u = \theta u$, but $L_T = L(T) + (e+1)I$ and $L(T)$ is
positive semidefinite, so $\theta \ge e+1$.

Since $me/r \ge 1$ (each vertex in $S$ has $e$ neighbors outside $S$
and $|S| = m$, so at most $me$ vertices in $X \setminus S$ have a
neighbor in $S$), it follows that all eigenvalues of $Q$ except for
the smallest are not less than $e+1$. By interlacing, $\mu_m \ge e+1$.
\qed

\medskip\noindent
{\bf Proof} (of the theorem).
Since $\mu_m \ge 0$ we are done if $d_m \le m-2$.
So, suppose that $d_m \ge m-1$.

Let $\Gamma$ have vertex set $X$, and let $x_i$ have degree $d_i$
$(1 \le i \le n)$. Put $S = \{x_1,\ldots,x_m\}$.
Put $e = d_m - m + 1$, then we have to show $\mu_m \ge e+1$.

Each point of $S$ has at least $e$ neighbours outside.
If each point of $S$ has at least $e+1$ neighbours outside,
then we are done by the lemma. And if not, then a point in $S$
with only $e$ neighbours outside is adjacent to all other
vertices in $S$, and we are done by the lemma, unless $e = 0$.

\medskip
Suppose first that $\Gamma$ is $K_m$ with a pending edge attached,
possibly together with some isolated vertices. Then $\Gamma$ has
Laplacian spectrum $m+1$, $m^{m-2}$, $1$, $0^{n-m}$, with exponents
denoting multiplicities, and equality holds.
And if $\Gamma$ is $K_m + K_2 + (n-m-2)K_1$, it has
spectrum $m^{m-1}$, $2$, $0^{n-m}$, and the inequality holds.

Let $T$ be the set of vertices of $S$ with at most $m-2$
neighbours in $S$. The case $T=\emptyset$ has been treated above.
For each vertex $s \in T$ delete all edges except one between $s$
and $X\setminus S$. Now the row of $L_S$ indexed by $s$
gets row sum $1$. Since $d_m=m-1$ we can always do so.
Also delete all edges inside $X\setminus S$, and possible isolated vertices.
By interlacing, $\mu_i$ has not been increased, so it suffices
to show that for the remaining graph $\mu_m\geq 1$.

Again consider the partition of $X$ into $m+1$ parts consisting of
$\{s\}$ for each $s\in S$, and $X\setminus S$,
and let $Q$ be the corresponding quotient matrix of $L$.
By interlacing it suffices to show that the second smallest
eigenvalue of $Q$ is at least 1.
Put $r=|X\setminus S|$ and $t=|T|$, then $0<r\leq t$, and
$$
Q = \left( \begin{array}{ccc}
mI-J & -J & {\bf 0} \\
  -J & L_T & -{\bf 1} \\
{\bf 0}^\top & -{\bf 1}^\top/r & t/r \\
\end{array}\right)
$$
($J$ is the all-ones matrix, and ${\bf 0}$ and ${\bf 1}$ denote the all-zeros
and the all-ones vector, respectively).
Now $Q$ has a $3\times 3$ quotient matrix
$$
R = \left( \begin{array}{ccc}
t & -t & 0 \\
t-m & m-t+1 & -1 \\
0 & -t/r & t/r \\
\end{array}\right)
$$
The three eigenvalues of $R$ are $0\leq x\leq y$ (say). We easily have that
$$ (1-x)(1-y) = \det(I-R) = t-1+(m-1)(t/r-1) \geq 0\ ,$$
which implies that $x\geq 1$ (since $x\leq y\leq 1$ contradicts
$x+y=\mbox{trace}\, R > m+1$). These three values are also eigenvalues of
$Q$ with (right) eigenvectors constant over the partition.
The remaining eigenvalues have (left) eigenvectors that are orthogonal to the
characteristic vectors of the partition, and these eigenvalues remain
unchanged if a multiple of $J$ is added to a block of the partition of $Q$.
So they are also eigenvalues of
$$
Q' = \left( \begin{array}{ccc}
mI & O & {\bf 0} \\
O & L_T & {\bf 0} \\
{\bf 0}^\top & {\bf 0}^\top & 1 \\
\end{array}\right),
$$
which are at least 1 since $L_T = L(T)+(m-t+1)I$ and $L(T)$ is
positive semidefinite. So we can conclude that $\mu_m\geq 1$.
\qed

\section{Equality}
There are many cases of equality (that is, $\mu_m = d_m - m + 2$),
and we do not have a complete description.

\medskip
For $m = 1$ we have equality, i.e., $\mu_1 = d_1 + 1$,
if and only if $\Gamma$ has a vertex adjacent to all other vertices.

\medskip
For $m = n$ we have equality, i.e., $0 = \mu_n = d_m-m+2$,
if and only if the complement of $\Gamma$ has maximum degree 1.

\medskip
The path $P_3 = K_{1,2}$ has Laplace eigenvalues 3, 1, 0
and degrees 2,~1,~1 with equality for $m = 0,1,2$,
and is the only graph with equality for all $m$.

\medskip
The complete graph $K_m$ with $a$ pending edges attached at
the same vertex has spectrum $a+m$, $m^{m-2}$, $1^a$, $0$,
with exponents denoting multiplicities.
Here $d_m = m-1$, with equality for $m$ (and also for $m = 1$).

\medskip
The complete graph $K_m$ with $a$ pending edges attached at
each vertex has spectrum
$\frac{1}{2}(m+a+1 \pm \sqrt{(m+a+1)^2 - 4m})^{m-1}$, $a+1$,
$1^{m(a-1)}$, $0$, with $\mu_m = a+1 = d_m-m+2$.
% m=2 a=1 gives P_4

\medskip
The complete bipartite graph $K_{a,b}$ has spectrum
$a+b$, $a^{b-1}$, $b^{a-1}$, $0$.
For ($a = 1$ or $a \ge b$) and $b \ge 2$ we have $d_2 = a = \mu_2$.
This means that all graphs $K_{1,b}$, and all graphs between
$K_{2,a}$ and $K_{a,a}$ have equality for $m = 2$.

\medskip
The following describes the edge-minimal cases of equality.

\begin{Proposition}
Let $\Gamma$ be a graph satisfying $\mu_m = d_m - m + 2$
for some $m$, and such that for each edge $e$ the graph
$\Gamma \setminus e$ has a different $m$-th largest degree
or a different $m$-th largest eigenvalue. Then one of the
following holds.

(i) $\Gamma$ is a complete graph $K_m$ with a single pending edge.

(ii) $m = 2$ and $\Gamma$ is a complete bipartite graph $K_{2,d}$.

(iii) $\Gamma$ is a complete graph $K_m$ with $a$ pending edges
attached at each vertex. Here $d_m = m+a-1$.
\end{Proposition}

{\bf Proof} This is a direct consequence of the proof of the main result.
\qed

\medskip
Many further examples arise in the following way.
Any eigenvector $u$ of $L = L(\Gamma)$ remains eigenvector
with the same eigenvalue if one adds an edge between two
vertices $x$ and $y$ for which $u_x = u_y$.
If $\Gamma$ had equality, and adding the edge does not change
$d_m$ or the index of the eigenvalue $\mu_m$, then the graph
$\Gamma'$ obtained by adding the edge has equality again.

\medskip
The eigenvector for the eigenvalue $a+1$ for $K_m$ with $a$ pending
edges attached at each vertex, is given by:
$1$ on the vertices of degree 1, and $-a$ on the vertices
in the $K_m$.
So, equality will persist when arbitrary edges
between the outside vertices are added to this graph,
as long as the eigenvalue keeps its index and $d_m$ does not change.

\medskip
The eigenspace of $K_{a,b}$ for the eigenvalue $a$ is given by:
values summing to 0 on the $b$-side, and $0$ on the $a$-side.
Again we can add edges.

\medskip
For example, the graphs $K_{2,d}$ with $d \ge 2$ have
$d_2 = d = \mu_2$ with equality for $m = 2$.
Adding an edge on the 3-side of $K_{2,3}$
gives a graph with spectrum 5, 4, 3, 2, 0,
and the eigenvalue 3 is no longer 2nd largest.
Adding an edge on the 4-side of $K_{2,4}$ gives a graph
with spectrum 6, 4, 4, 2, 2, 0, and adding two disjoint
edges gives 6, 4, 4, 4, 2, 0, and in both cases
we still have equality for $m = 2$.


\begin{thebibliography}{9}

\bibitem{GroneMerris94}
R. Grone \& R. Merris,
{\it The Laplacian spectrum of a graph II},
SIAM J. Discr. Math. {\bf 7} (1994) 221--229.

\bibitem{Guo07}
Ji-Ming Guo,
{\it On the third largest Laplacian eigenvalue of a graph},
Lin. Multilin. Alg. {\bf 55} (2007) 93--102.

\bibitem{Haemers95}
W. H. Haemers,
{\it Interlacing eigenvalues and graphs},
Linear Alg. Appl. {\bf 226--228} (1995) 593--616.

\bibitem{LiPan00}
Jiong-Sheng Li \& Yong-Liang Pan,
{\it A note on the second largest eigenvalue of the Laplacian matrix
of a graph}, Lin. Multilin. Alg. {\bf 48} (2000) 117--121.

\end{thebibliography}
\end{document}
