# Efficiently remove nodes from a connected graph

Suppose you have a connected graph and want to remove k nodes such that the result is still connected. How could you do this efficiently?

It occurs to me that you could find any spanning tree, say by a tree search of any kind. Identify all leaves in the spanning tree, all of these can be removed without disconnecting the remaining vertices. If you have more than k leaves then you're done, but in any tree you're only guaranteed 2 leaves. So you may need to reiterate the process until you've removed k vertices.

That implies O(k) runs of a tree search. Does a more efficient algorithm exist? I don't think you can just look for articulation points or bridge edges because removing a single vertex may suddenly make other vertices which weren't articulation points now turn into articulation points.

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.