Note on deleting a vertex and weak interlacing of the Laplacian spectrum

Abstract

The question of what happens to the eigenvalues of the Laplacian of a graph when
we delete a vertex is addressed. It is shown that
λ_i − 1 ≤ λ^v_i ≤ λ_i+1,
where λ_i is the ith smallest eigenvalues of the Laplacian of the original graph and λ^v_i is the ith smallest eigenvalues of the Laplacian of the graph G[V −v]; i.e., the graph obtained after removing the vertex v. It is shown that the average number of leaves in a random spanning tree F(G) > 2|E|e^-1/α / λ_n , if λ₂ > αn.