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
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.