Eigenvalue of Laplacian of a complete graph $h\leq n/2$ edges removed.

Question

Show that for the graph, G, that is obtained by removing h disjoint edges from a complete, unweighted graph, K, on n vertices, with n ≥ 2h, the eigenvalues of the Laplacian L(G) are n − 2 with multiplicity h, n with multiplicity n − h − 1 and 0 with multiplicity 1

Answer 1

Let $\beta=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}$, and $B$ be the $n \times n$ block diagonal matrix with exactly $h$ blocks $\beta$, and zeroes everywhere else.

Let $J$ be the $n \times n$ matrix with ones everywhere.

For a suitable ordering of your nodes, the Laplacian is $L=nI_n-J-B$.

Note that $J$ and $B$ are symmetric and $JB=BJ=0$.

So there is an orthogonal matrix $U$ such that $D_J=U^TJU$, $D_B=U^TBU$ are diagonal, with disjoint “supports”.

It is well-known that outside from $0$, $J$ has a single eigenvalue $n$. It can also be seen that $B$ has $n-h$ eigenvalues $0$ and $h$ eigenvalues $2$ (because each $\beta$ has one eigenvalue $0$ and, using its trace, one eigenvalue $2$).

As a consequence, $L$ has $h$ eigenvalues $n-2$, $1$ eigenvalue $0$ and the rest are eigenvalues $n$.