Why is the largest eigenvalue of a laplacian matrix equal to the number of nodes in the graph?

Question

I've been posed the following question:

The spectrum of the Laplacian matrix $Q$ of the complete graph $K_{N}$ on $N$ nodes is:

1. $1^{[1]}$ and $N^{[N-1]}$
2. $0^{[1]}$ and $(N-1)^{N-1}$
3. $1^{[1]}$, $0^{[1]}$, and $(N-1)^{[N-2]}$
4. None of the above.

Here, the $\mu^{[m]}$ denotes multiplicity (how many times that value appears).

My solution to the question would be to choose (4) because the largest eigenvalue of the Laplacian is (by Gerschgorin) $\lambda_{1} \leq d_{max}$ where $d_{max}$ is the largest degree in the graph. The largest degree for a complete graph is $N-1$, (and it is the degree for all nodes in the complete graph). So we should expect to find that the eigenvalues contain at least one zero, and all others should be $d_{max}$. That makes the expected correct answer $0^{[1]}$ and $(N-1)^{[N-1]}$

However, apparently the correct answer is: $0^{[1]}$ and $(N)^{[N-1]}$.

Why is the is the case? Have I made a mistake in my graph properties here?

Answer 1

The Laplacian of the complete graph $K_n$ with $n$ nodes is $L_n = n I_n - J_n$, where $I_n$ is the identity matrix and $J_n$ is the matrix full of $1$'s. If $v$ is the vector of all 1's, then $L_n v = n v - J_n v = nv - nv = 0$. Also, if $w$ is a vector whose components sum to $0$, then $L_n w = nw - J_n w = nw$. So we can see that indeed the eigenvalues of the Laplacian of $K_n$ are $(0^{[1]}, n^{[n-1]})$.

Answer 2

I don't know why you are telling that $\lambda_1 \leq d_{max}$. Because we have a result from Brouwer and Haemers that says $\lambda_i\geq d_i-i+2$ for all $1\leq i\leq n$. IT means that $\lambda_1\geq d_1+1$.