Consider the Laplacian $L$ of some simple graph $G$ with at least one edge. As usual, $L=D-A$ where $D$ is the diagonal matrix with elements $D_{ii}=d_i$ where $d_i$ is the degree of node $i$ and matrix $A$ is the adjacency matrix with elements $A_{ij}=1$ if there is an edge between nodes $i,j$ and otherwise $0$.
It is well known that $\mathrm{Tr}(L)=\sum_i\lambda_i=\sum_id_i$ where $\lambda_i$ are the eigenvalues of $L$. Therefore if a random edge is deleted from $G$ all three quantities decrease by $2$. But in principle if $G$ is not too small, maybe some eigenvalues could increase a little bit and others would decrease such that the sum decreases by exactly $2$. I investigated this numerically with Erdös-Renyi graphs and found no such instances: in all cases every eigenvalue always decreases or stays the same, i.e. is non-increasing. I considered some tens of thousands of cases and different sizes.
Can it be shown that not only does the sum of the eigenvalues decrease, but also every single eigenvalue is non-increasing when an edge is deleted? Or can you perhaps come up with a counterexample?
Best Answer
Yes, it is a known property of the Laplacian. It is a specific instance of interlacing properties, see for instance ``Eigenvalue Interlacing in Graphs'' by Porto and Allem in Proceeding Series of the Brazilian Society of Computational and Applied Mathematics.
A better reference would be the following, but I'm not sure if it is available:
F. Hall, K. Patel and M. Stewart. Interlacing results on matrices associated with graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 68:113–127, 2009.
If $\lambda_i,\theta_i$ are the eigenvalues of $G$ and $H=G-e$, respectively, then we have for all $i$ $$\lambda_i\geq\theta_i$$