Articulation Points and Depth-First Search

Let G be a connected, undirected graph and let T be a depth-first search tree of G.

Lemma 1: If (u,v) is an edge in G that is not in T, then either u is a proper ancestor of v in T or v is a proper ancestor of u in T.

Proof: Exercise.

Theorem 2: A vertex a is an articulation point iff:

1. either a is the root of T and has more than one child, or
2. a is not the root of T and it has a child b such that there is no back edge from a descendant of b (including b itself) to a proper ancestor of a.

Proof:

1. Let a be the root of T. Suppose it has at least two children b and c. By lemma 1, there can be no edge between b and c in G. Therefore, every path in G between b and c must pass through the vertex a making a an articulation point in G.

   Conversely, suppose a has only one child b in T. Then all vertices in G, except a, are descendants of b in T. This would imply that for every pair of distinct vertices u and v that are descendants of b in T, there is a path between u and v that does not pass through a. In this case, a is not an articulation point.

2. Let a be a non-root vertex in T. Let f be the parent of a in T. Suppose it has a child b such that there is no back edge from any descendant of b to a proper ancestor of a. Then every path between b and f must pass through the vertex a making a an articulation point in G.

   Conversely, suppose a is an articulation point in G. Let x and y be two distinct vertices such that every path in G between x and y passes through a. At least one of x and y must be a proper descendant of a (why?). Let x be a proper descendant of a. Let b be a child of a such that x is a descendant of b.

   Assume that the condition of the theorem does not hold. (That is, for all children b of a there is a descendant of b from which there is a back edge to a proper ancestor of a.) Then the following conditions must be true:

   • There is a back edge from a descendant d of b to a proper ancestor d of a. (why?). This gives a path between x and d that does not pass through a.
   • The vertex y is also a proper descendant of a. (Suppose not. Then there is a path from y to d that does not pass through a. This together with the path between d and x will give a path between x and y contradicting the hypothesis that a is an articulation point.)
   • The vertex y cannot be descendant of b. (why?).
   Let c be the child of a such that y is a descendant of c. Since we assumed that the condition does not hold, there is a back edge from a descendant e of c to a proper ancestor e of a. Then there is a path between x and y that does not pass through a contradicting our assumption that every path between x and y passes through a. Thus the condition must hold.

COMPUTING THE ARTICULATION POINTS: Let a be a vertex that is not the root of T. (The root of T as an articulation point if it has more than one child.)

Define LOW(b), for each vertex b, as the minimum over all vertices c of DFSNumber(c) such that there is a path from b to c consisting of 0 or more tree edges and at most 1 back edge. (That is, LOW(b) gives the DFSNumber of the vertex closest to the root of T that is reachable from a descendant (including itself) of b using at most 1 back edge.) Then, the vertex a is an articulation point iff it has a child b such that .

So, to compute the articulation points of G, we compute their LOW values. Initially, set . When a back edge (b,c) is seen, LOW(b) is set to the minimum of DFSNumber(c) and LOW(b). When returning to b after finishing with an immediate descendant d, LOW(b) is set to the minimum of LOW(d) and LOW(b).

• About this document ...