ELA, Volume 16, pp. 68-72, February 2007, abstract.

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

Zvi Lotker

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 

  lambda_{i} - 1 <= lambda^{v}_{i} <= lambda_{i+1},

where lambda_{i} is the ith smallest eigenvalues of the 
Laplacian of the original graph and lambda^{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/alpha)/lambda_n, 

if lambda_2> n(alpha).