Efficiently remove nodes from a connected graph
Let $G$ be your graph. Compute any spanning tree $T$ of $G$. Perform a postorder visit of $T$, and keep track of the set $D$ of the first $k$ vertices visited ($T$ and $D$ can be computed by the same DFS visit).

The graph $G'$ obtained by deleting the vertices in $D$ from $G$ is still connected (and $T-D$ is a spanning tree of $G'$).
To prove this notice that if $v \in D$, then all descendants of $v$ in $T$ must belong to $D$ as well.