Does an expander remain an expander after removing few vertices and edges?

Question

Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices. Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. Call $G'_n$ the largest connected component of the resulting graph. Are the ($G'_n$) still expanders ?

Answer 1

No. Assume that $G_n$ has bounded degree (this is probably an assumption of yours).

By removing $0$ vertices and $O(\log n)$ edges, you can make sure that $G'_n$ has $\geq n/2$ vertives and contains a "segment of length $\geq c\log n$" (that is a sequence $x_1,\dots,x_{k}$ of vertices in $G'_n$ such that $k \geq c \log n$ and for all $i <k $, the set of neighbours of $x_i$ is $\{x_{i-1},x_{i+1}\}$ (without $x_{0}$ if $i=1$). In particular the boundary of $\{x_1,\dots,x_{k-1}\}$ reduces to $\{x_k\}$, so $G'_n$ is not an expander sequence.

There are probably many ways to justify the preceding ; here is one. Pick a spanning tree $T$ in $G_n$. By the bounded degree assumption, $T$ has diameter $\geq c' \log n$, so there is a path $x_1,\dots,x_{2k}$ in $T$ of length $2k = c \log n$. By reversing the order of this path you can assume that ($*$) by removing the edge between $x_k$ and $x_{k+1}$ in the tree, the subtree containing $x_1$ contains less than half of the vertices. Remove from $G_n$ all the $O(\log(n))$ edges adjacent to $x_1,\dots,x_{k-1}$ except those that appear in $T$. Then the connected component of $x_1$ in the remaining graph contains more that half of the vertices of $G_n$ by ($*$). So $x_1$ belongs to $G'_n$, and by construction $x_1,\dots,x_k$ is a segment in $G'_n$.