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]}$ and $N^{[N-1]}$
- $0^{[1]}$ and $(N-1)^{N-1}$
- $1^{[1]}$, $0^{[1]}$, and $(N-1)^{[N-2]}$
- 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?
Best Answer
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]})$.