Standard Laplacian matrix of a connected graph with $N$ vertices

Question

Can anybody help me to proof the expression $$L_K *L_G=N L_G$$ where $L_K$ is the Laplacian matrix of a complete graph on $N$ vertices, $L_G$ is the Laplacian matrix of any connected graph with $N$ vertices, and $*$ is just standard matrix multiplication?

Laplacian matrix is standard Laplacian matrix as defined on page $5$ of this document. The graph is simple (it does not have self loops) and connected.

Thanks in advance

Answer 1

Well, there are two key observations:

• $L_K=N I-J$, where $I$ is the identity matrix and $J$ is the all-1-matrix.
• $L_G * J=0$ for any graph $G$, because each entry of the product is the sum of all entries of some row of $L_G$, which of course is zero.

Now your formula follows.