# Upper bound on least eigenvalue of a graph

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:

$$$$\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \mu_2 \leq \ldots \leq \lambda_{n-1} \leq \mu_{n-1} \leq \lambda_n$$$$

$$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

$$$$\lambda_1 \leq \mu_1$$$$

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?

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

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$$.