Let $c: V \to \{1, \ldots, k\}$ be a proper $k$-coloring with $k = \chi(G)$. Partition $V = S_1 \cup \cdots \cup S_k$ into color classes (independent sets). Let $n_i = |S_i|$ and define vectors $x_i = \mathbf{1}_{S_i} - \frac{n_i}{n}\mathbf{1}$ for each color class, where $\mathbf{1}_{S_i}$ is the indicator vector of $S_i$.

Each $x_i$ is orthogonal to $\mathbf{1}$ (the eigenvector for $\lambda_1$), so $x_i$ lies in the span of eigenvectors for $\lambda_2, \ldots, \lambda_n$.

Computing $x_i^T A x_i$. Since $S_i$ is independent: $\mathbf{1}_{S_i}^T A \mathbf{1}_{S_i} = 0$. Also $\mathbf{1}^T A \mathbf{1} = 2|E|$. So: $x_i^T A x_i = 0 - 2\frac{n_i}{n}\mathbf{1}_{S_i}^T A\mathbf{1} + \frac{n_i^2}{n^2}\mathbf{1}^T A\mathbf{1} = -\frac{2n_i d_i}{n} + \frac{2n_i^2 |E|}{n^2}$ where $d_i = \sum_{v \in S_i} \deg(v)$.

Summing over color classes. $\sum_i x_i^T A x_i = -\frac{2}{n}\sum_i n_i d_i + \frac{2|E|}{n^2}\sum_i n_i^2$. Since $\sum_i d_i = 2|E|$ (each edge contributes to two color classes) and $\sum n_i = n$:

By Cauchy-Schwarz, $\sum n_i^2 \geq n^2/k$, so the second term is $\geq 2|E|/k$.

Alternative approach (cleaner). Let $X$ be the $n \times k$ matrix with $X_{vi} = 1$ if $c(v) = i$. Then $B = X(X^TX)^{-1}X^T - \frac{1}{n}J$ is a projection-like matrix orthogonal to $\mathbf{1}$.

Since $x_i \perp \mathbf{1}$ and $x_i$ is in the span of eigenspaces for $\lambda_2, \ldots, \lambda_n$: $x_i^T A x_i \geq \lambda_n \|x_i\|^2$ (by Rayleigh quotient).

Summing: $\sum_i x_i^T A x_i \geq \lambda_n \sum_i \|x_i\|^2$.

Now $\sum_i \|x_i\|^2 = \sum_i (n_i - n_i^2/n) = n - \sum n_i^2/n$.

Also: $\sum_i x_i^T A x_i = \mathrm{tr}(A B') = -2|E|/n + 2|E|\sum n_i^2/n^2 \cdot n/(n-1)$... Let us use yet another clean approach:

Shortest proof. The matrix $C = A - \lambda_n I$ is positive semidefinite restricted to the space orthogonal to the $\lambda_n$-eigenspace, but more usefully: $A - \lambda_n I \succeq 0$ is false in general. Instead: for independent set $S_i$, define $e_i = \mathbf{1}_{S_i}/\sqrt{n_i}$. Then $e_i^T A e_j = |E(S_i, S_j)|/\sqrt{n_in_j} \geq 0$ for $i \neq j$ and $e_i^T A e_i = 0$. The $k \times k$ matrix $M_{ij} = e_i^T A e_j$ has $M_{ii} = 0$ and $M_{ij} \geq 0$, and all eigenvalues of $M$ lie in $[\lambda_n, \lambda_1]$. Since $\mathrm{tr}(M) = 0$ and eigenvalues of $M$ are $\geq \lambda_n$, and at least one eigenvalue $\leq \lambda_1$: $0 = \mathrm{tr}(M) \geq \lambda_1 + (k-1)\lambda_n$, giving $k \geq 1 - \lambda_1/\lambda_n$. $\square$