On the extreme eigenvalues of regular graphs

AbstractIn this paper, we present an elementary proof of a theorem of Serre concerning the greatest eigenvalues of k-regular graphs. We also prove an analogue of Serre's theorem regarding the least eigenvalues of k-regular graphs: given ε>0, there exist a positive constant c=c(ε,k) and a non-negative integer g=g(ε,k) such that for any k-regular graph X with no odd cycles of length less than g, the number of eigenvalues μ of X such that μ⩽-(2-ε)k-1 is at least c|X|. This implies a result of Winnie Li