Least eigenvalue of adjacency matrix of regular graph The greatest eigenvalue of the adjacency matrix of a $d$-regular graph is $\lambda_1 = d$.
What is the best way to show that the least eigenvalue is at least $-d$?
 A: The adjacency matrix has all nonnegative entries, so the Perron-Frobenius theorem applies.
A: the number of closed walks of length $k$ is $\sum \limits_{i=1} ^n \lambda_i ^k$. If the eigenvalue of largest magnitude were negative this expression would be negative for large odd $k$.
A: While the result you want is an easy consequence of Perron-Frobenius, for regular graphs, there is a simple argument. Suppose $z$ is an eigenvector and $Az=\lambda z$. Let $|z|$ denote the vector got be replacing each entry of $z$ by its absolute value. Then
\[
  \lambda z_i = \sum_{j\sim i} z_j
\]
and hence using the triangle inequality, we have
\[
  |\lambda| |z_i| \le \sum_{j\sim i} |z_j|.
\]
Choose $i$ so $|z_i|$ is maximal, then we find that
\[
  |\lambda| |z_i| \le k|z_i|
\]
and therefore $|\lambda|\le k$. (This actually proves that the maximum valency of $G$ is an upper bound on $|\lambda|$ and, with a little effort, you can prove that equality holds if and only if $G$ is regular.)
A: By Gershgorin circle theorem, for any eigenvalue $\lambda$ of the adjacency matrix of a $d$-regular graph, one has $\lambda\in[-d,d]$.
