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).