Proof for a property of graph laplacian and its complement? 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$$
 A: 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.
