Least eigenvalue of adjacency matrix of regular graph

Question

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

Answer 1

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

Answer 2

The adjacency matrix has all nonnegative entries, so the Perron-Frobenius theorem applies.