Problem from Biggs graph theory From Norman Biggs, Algebraic Graph Theory, 2nd edition 1993, p. 13, exercise 2i:

2i. An upper bound for the largest eigenvalue. Suppose that the eigenvalues of $\Gamma$ are $\lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1}$, where $\Gamma$ has $n$ vertices and $m$ edges. From 2h we obtain $\sum \lambda_i = 0$ and $\sum \lambda_i^2 = 2m$. It follows that $$\lambda_0 \leq \left(\dfrac{2m\left(n-1\right)}{n}\right)^{\frac{1}{2}}.$$

I have tried to solve this problem but I just can't.  The matrix of a graph on $n$ vertices is $n\times n$ with all entries $0$ or $1$, and diagonal $0$.
My attempt: We know that for such a matrix $|\lambda_0|\leq n-1$. \begin{eqnarray*}
\lambda_{0}^{2} & = & \frac{\lambda_{0}^{2}}{n}+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\
 & = & \frac{\left|\lambda_{0}\right|^{2}}{n}+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\
 & \leq & \left|\sum_{1\leq i}\lambda_{i}\right|\left(\frac{n-1}{n}\right)+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\
 & \leq & \sum_{1\leq i}\left|\lambda_{i}\right|\left(\frac{n-1}{n}\right)+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\
 & \leq & \sum_{1\leq i}\lambda_{i}^{2}\left(\frac{n-1}{n}\right)+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\
 & = & \sum\lambda_{i}^{2}\left(\frac{n-1}{n}\right)\\
 & = & \frac{2m(n-1)}{n}
\end{eqnarray*}
I think everything is ok until the last $\leq$. This would be true if all the eigenvalues were integers, but as someone pointed out, the eigenvalues of these matrices don't have to be integers.
 A: We need to show that $\lambda_0 \leq \left(\dfrac{2m\left(n-1\right)}{n}\right)^{\frac{1}{2}}$. It is clearly enough to prove that $\left|\lambda_0\right| \leq \left(\dfrac{2m\left(n-1\right)}{n}\right)^{\frac{1}{2}}$. In other words, we need to show that $n \lambda_0^2 \leq 2m \left(n-1\right)$. In other words, we need to show that $n \lambda_0^2 \leq \left(\sum_i \lambda_i^2\right) \left(n-1\right)$ (since $\sum_i \lambda_i^2 = 2m$). Rewriting $\sum_i \lambda_i^2$ as $\lambda_0^2 + \sum_{i\geq 1} \lambda_i^2$, we transform this into $n \lambda_0^2 \leq \left(\lambda_0^2 + \sum_{i\geq 1} \lambda_i^2\right) \left(n-1\right)$. In other words, we need to prove that $n \lambda_0^2 \leq \left(n-1\right) \left(\lambda_0^2 + \sum_{i\geq 1} \lambda_i^2\right)$. Upon subtracting of $\left(n-1\right)\lambda_0^2$, this simplifies to $\lambda_0^2 \leq \left(n-1\right) \sum_{i\geq 1} \lambda_i^2$. Since $0 = \sum_i \lambda_i = \lambda_0 + \sum_{i\geq 1}\lambda_i$, we have $\lambda_0 = - \sum_{i\geq 1}\lambda_i$ and thus $\lambda_0^2 = \left(\sum_{i\geq 1}\lambda_i\right)^2$. Hence, the inequality we must prove, that is, $\lambda_0^2 \leq \left(n-1\right) \sum_{i\geq 1} \lambda_i^2$, rewrites as $\left(\sum_{i\geq 1}\lambda_i\right)^2 \leq \left(n-1\right) \sum_{i\geq 1} \lambda_i^2$. But this follows immediately from the Cauchy-Schwarz inequality.
