Bound on Largest Eigenvalue of Laplacian Matrix of a Graph

729 Views Asked by At

I am self-studying graph (spectral) theory and trying to prove the following problem. Assume we have a graph $G = (V,E)$ with adjacency matrix $A$ and diagonal degree matrix $D$ (where each diagonal entry represents the degree of the corresponding node). Define the Laplacian matrix $L = D-A$. Suppose that the number of non-isolated vertices in this graph is $\tilde{n}$, then the claim is that the largest eigenvalue of $L$, $\lambda_1$, must satisfy $$\lambda_1 \leq \tilde{n}$$

I am not sure how to show this. The trace of $L$, equals the sum of degrees of the graph, also equals the sum of all eigenvalues. The algebraic multiplicity of the eigenvalue zero indicates the number of connected components, but I am not sure how to precede from here.

Any thought is appreciated.