For random d-regular graphs on N vertices with 1 \ll d \ll N^{2/3}, we develop a d^{-1/2} expansion of the local eigenvalue distribution about the Kesten-McKay law up to order d^{-3}. This result is valid up to the edge of the spectrum. It implies that the eigenvalues of such random regular graphs are more rigid than those of Erdős-Rényi graphs of the same average degree. As a first application, for 1 \ll d \ll N^{2/3}, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by (2 + o(1)) \sqrt{d - 1}. As a second application, for N^{2/9} \ll d \ll N^{1/3}, we prove that the extremal eigenvalues are concentrated at scale N^{-2/3} and their fluctuations are governed by Tracy-Widom statistics. Thus, in the same regime of d, 52% of all d-regular graphs have second-largest eigenvalue strictly less than 2 \sqrt{d - 1}.
