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?
Best Answer
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$.