Let $G$ be a $n$-vertex $d$-regular graph. Let $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ be the eigenvalues of the adjacency matrix $A_G$ of $G$ and $\lambda\geq \max\{|\lambda_2|, |\lambda_n|\}$. (I.e., $G$ is a $(n,d,\lambda)$-graph.)
Prove that the diameter of $G$ is at most $\lceil \log n / \log (d/\lambda) \rceil$.
I think this problem is related to the proofof Alon-Boppana bound, but I don't have any idea how to prove.
Best Answer
Have a look at "Chung, F. R. K. (1989). Diameters and Eigenvalues. Journal of the American Mathematical Society, 2(2), 187."
Here is the proof (obviously not my work).