1
$\begingroup$

I found this result in a paper: "Much less is known about the least eigenvalue [in comparison to the spectral radius]. Recall first that the least eigenvalue of any graph is non-positive. It is equal to zero only for totally disconnected graphs. Otherwise, for graphs with at least one edge, it is less than or equal to $-1$ (by the Interlacing Theorem)."

I am curious how to prove the last statement through employing the interlacing theorem for real symmetric matrices. I just can't seem to crack it. Here's my attempt:

Let $G$ be a non-empty graph with adjacency matrix $A$, meaning it has at least one edge. Since $G$ has at least one edge, there exists a vertex $v$ in the graph $G$ with a degree of at least $1$ (i.e., it has at least one neighboring vertex). Let $G'$ be the subgraph of $G$ obtained by removing vertex $v$ and all its incident edges. Let $B$ be the adjacency matrix of $G'$. $B$ is obtained by removing the $v$-th row and the $v$-th column of $A$.

Now we can apply the interlacing theorem:

Since $A$ is a real symmetric matrix, and $B$ is obtained by removing one row and one column from $A$, the eigenvalues of $B$ interlace the eigenvalues of $A$: if $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n$ are the eigenvalues of $A$ and $\mu_1 \leq \mu_2 \leq \ldots \leq \mu_{n-1}$ are the eigenvalues of $B$, then:

\begin{equation} \lambda_1 \leq \mu_1 \leq \lambda_2 \leq \mu_2 \leq \ldots \leq \lambda_{n-1} \leq \mu_{n-1} \leq \lambda_n \end{equation}

$G'$ is obtained from $G$ by removing a vertex and its incident edges, which means $G'$ has fewer edges than $G$. Since $G$ is non-empty and $G'$ has fewer edges, $G'$ cannot be a complete graph. The smallest eigenvalue of a complete graph is $0$, so the smallest eigenvalue of $G'$, $\mu_1$, must be strictly less than $0$.

So by the interlacing property

\begin{equation} \lambda_1 \leq \mu_1 \end{equation}

But here's where the proof breaks down, because I'm not sure where $-1$ comes into play, and it's not like I can claim the eigenvalues must be integers. How can I prove the required statement?

$\endgroup$
1
  • $\begingroup$ Sketch: Argue that the adjacency matrix can be diagonalized, And the trace is $0$ so the sum of the eigenvalues is $0$. $\endgroup$
    – lulu
    Commented Apr 22, 2023 at 22:11

1 Answer 1

1
$\begingroup$

The graph $H$ with two vertices and a single edge between them has two eigenvalues: $\beta_1 = -1$ and $\beta_2 = 1$.

If a graph $G$ has eigenvalues $\lambda_1 \le \lambda_2 \le \dots \le \lambda_n$ and contains the induced subgraph $H$ (that is, contains an edge), then the interlacing theorem says that $\lambda_1 \le \beta_1 \le \lambda_{n-1}$ and $\lambda_2 \le \beta_2 \le \lambda_n$. In particular, $\lambda_1 \le -1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .