7.39

Idea
Do one depth-first search of the (connected) graph. Every tree edge of the DFS goes from a vertex to its already visited parent, so the children of a vertex are the only vertices that can be separated from the rest by that parent. Therefore, if all children are removed before the parent, deleting the parent can never disconnect the part that is still present. This gives the required order: delete vertices in the reverse order of their DFS finishing times (i.e. in post-order, leaves first, root last).

Algorithm (O(n+m))
DFS(G):
  stack = empty list        # holds post-order
  visited = { }
  procedure visit(v):
    visited.add(v)
    for each w adjacent to v if w not in visited:
      visit(w)
    stack.append(v)      # push when subtree is finished
  visit(any start vertex)
  return stack        # deletion order

Correctness proof
Induct from the end of stack (the first vertex to be removed) toward its front.
Induction hypothesis: after removing the k deepest vertices of the DFS tree (the last k entries written to stack) the subgraph induced by the remaining vertices is still connected.
• Base k = 0: the whole graph is connected by assumption.
• Step: let v be the next vertex to delete. All of its descendants in the DFS tree have already been removed, so every neighbor of v that is still present lies higher in the tree (its parent or an ancestor via a back edge). Thus the remaining vertices stay connected after deleting v.
By induction every deletion keeps connectivity, so the produced order is valid.

Running time
The DFS touches each vertex and edge once (Θ(n+m)). Building the stack and reading it back is Θ(n), so the whole algorithm is [math]O(n+m)[/math].

Back to Chapter 7