  We study the behavior of algebraic connectivity in a weighted graph that is
subject to site percolation, random deletion of the vertices. Using a refined
concentration inequality for random matrices we show in our main theorem that
the (augmented) Laplacian of the percolated graph concentrates around its
expectation. This concentration bound then provides a lower bound on the
algebraic connectivity of the percolated graph. As a special case for
$(n,d,\lambda)$-graphs (i.e., $d$-regular graphs on $n$ vertices with
non-trivial eigenvalues less than $\lambda$ in magnitude) our result shows
that, with high probability, the graph remains connected under a homogeneous
site percolation with survival probability $p\ge 1-C_{1}n^{-C_{2}/d}$ with
$C_{1}$ and $C_{2}$ depending only on $\lambda/d$.
