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 ?



Does an expander remain an expander after removing few vertices and edges?
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$.


