Proof for a property of graph laplacian and its complement?

Question

Here it says

Let $L(G)$ be the Laplacian of an undirected graph.

$L(G)+L(G^c)=n I_n-J_n$

Where $J_n$ is a matrix with all entries $1$.

Then how do we prove this (page $224$; eq. $5$):

$$\lambda_{n-i}(G^c)=n-\lambda_i(G), \qquad 1 \leq i < n$$

Answer 1

Rewrite $L(G^c)$ as $nI_n -e^T_n e_n -L(G)$, where $e_n$ is the all-ones $n$-tuple row vector, and $e^T_n e_n = J_n$. Note that $(e_n, 0)$ is still a trivial (row) eigenpair of $L(G^c)$: \begin{align} e_n L(G^c) &= n e_n I_n - e_n e^T_n e_n -e_n L(G) \\ &= n e_n - ne_n - 0 e_n \\ &= 0 e_n. \end{align} Then take a non-trivial (row) eigenpair of $L(G)$, i.e., $(x, \lambda_i(G))$ where $1 \leq i < n$. Since eigenvalue $\lambda_i(G)$ comes from a different kernel than eigenvalue $0$, it is true that $x e^T_n =0$. Then, \begin{align} x L(G^c) &= n x I_n - x e^T_n e_n -x L(G) \\ &= n x - 0 e_n - \lambda_i(G) x \\ &= (n-\lambda_i(G)) x. \end{align} Thus, $(x, n-\lambda_i(G))$ is an eigenpair of $L(G^c)$, for $1 \leq i < n$. Since the eigenvalues of $L(G)$ are sorted in a nonincreasing order ($\lambda_1(G) \geq \lambda_2(G) \geq \ldots \geq \lambda_n(G) = 0$), then the mapping $\lambda_i(G) \mapsto n-\lambda_i(G)$ is going to rearrange them in the wrong order. Letting $$\lambda_i (G^c) := n -\lambda_{n-i} (G) \text{ for } 1 \leq i < n,$$ or equivalently ($i \gets n-i$), $$\lambda_{n-i} (G^c) := n -\lambda_i (G) \text{ for } 1 \leq i < n,$$ is a turnaround.