Upper bound on the largest eigenvalue of a simple graph

Question

Let $X$ be a simple graph with $n$ vertices and $e$ edges and let $\lambda$ be an eigenvalue of $X$. Show that

$$ |\lambda| \leq \sqrt\frac{2e(n-1)}{n}$$

which is equivalent to

$$n\lambda^{2} \leq 2e(n-1)$$

I've been given an hint to consider the equality $\mathrm{tr}(A^{2}) = 2e$, where $A$ is the adjacency matrix of $X$, which I've already proved, and to use Cauchy-Schwarz inequality from Calculus. I tried to, but I can't figure out which values I'm supposed to consider in that inequality to prove the previous equivalent form.

I also know that $\mathrm{tr}(A^2)$ is the sum of the squares of all eigenvalues of $A$, so that it suffices to show that inequality for the largest module of an eigenvalue.

I would appreciate if someone helps me here.

Answer 1

Since you are considering a simple graph $\sum_{i=1}^n{\lambda_i}=\mathrm{tr}(A)=0$, and therefore $\lambda_1 = -\sum_{i=2}^n{\lambda_i}$. Now use this, $\mathrm{tr}(A^{2}) = 2e$ and Cauchy-Schwarz inequality to get

$$ \lambda_1^2=\left(-\sum_{i=2}^n{\lambda_i}\right)^2\leq (n-1)\sum_{i=2}^n\lambda_i^2=(n-1)(2e-\lambda_1^2). $$

Answer 2

Let $X$ be a regular graph of degree $d$. Then the largest eigen value is $d$. Total number of edges $e=\frac{nd}{2}$.
Hence $ed=\frac{nd^2}{2}$.
$d \leq n-1$ trivially. Substituting in above we get: $e(n-1) \geq \frac{nd^2}{2} = \frac{n|\lambda|^2}{2}$.

You can see that the inequality very loose for regular graph as we used the bound $d \leq n-1$.

For general case note that $Tr(A^2) = \sum_i d_i$ where $d_i$ is the degree of $i^{th}$ node. So replace $d$ with $\frac{\sum_i d_i}{n}$ in the above derivation. You need the inequality $n \lambda_1 \leq \sum_i \lambda_i^2 = Tr(A^2)=\sum_i d_i$ for general case.