$L$ be the Laplacian of $G$ with maximum eigenvalue $\lambda_1$, then $\lambda_1 \leq n$.

Question

Let $G$ be a graph with vertex set $V(G) = \{1, \ldots , n\}$. Let $L$ be the Laplacian of $G$ with maximum eigenvalue $\lambda_1$. Show that $\lambda_1 \leq n$.

Require some hints to prove it.

Answer 1

Let $u = (u_i)$ be the normalized eigenvector corresponding to $\lambda_1$. We have

$$\lambda_1 = u^T L u = \sum_{\{i,j\} \in E(G)} (u_i-u_j)^2$$

Since all terms of the form $(u_i - u_j)^2$ are non-negative, the sum on the right will only get larger when one replace $G$ by the complete graph $K_n$ which have more edges. This leads to

$$\lambda_1 \le \sum_{\{i,j\} \in E(K_n)}(u_i-u_j)^2 = \sum_{1 \le i < j \le n}(u_i - u_j)^2 = \frac12\sum_{i=1}^n\sum_{j=1}^n (u_i-u_j)^2\\ = n\left(\sum_{j=1}^n u_j^2\right) - \left(\sum_{i=1}^n u_i\right)^2 \le n $$