Question about the conditions to find articulation points in a graph

Question

I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.

In it, we first construct a DFS tree and store the following information for each vertex in the DFS tree:

• The traversal order at which we visited the vertex
• The highest reachable ancestor from the tree for each vertex

After constructing the tree, the author says one of the following conditions need to be satisfied for a vertex to be an articulation vertex:

• If the root has more than 1 child, it is an articulation point
• If we have an edge A -> B which is a bridge, then A is an articulation point
• If we have an edge A -> B (A is parent of B) and the highest reachable node from B is A, then A is an articulation point.

I wrote a program to test this and it works on the graphs I tested it against:

// lo[] contains highest index
// pre[] contains traversal order
private void dfsFindArticulationPoints(int node, int parent) {
    if(pre[node] != 0) {
        lo[parent] = Math.min(lo[parent], pre[node]);
        return;
    }
    
    pre[node] = index;
    lo[node] = index;
    index++;

    int childCount = 0;
    for(int child: graph[node]) {
        if(pre[child] != 0)
            childCount++;
        if(child == parent)
            continue;
        dfsFindArticulationPoints(child, node);
        lo[node] = Math.min(lo[child], lo[node]);

        // Check case 2 and 3
        if(node != 0 && pre[node] <= lo[child])
            articulationPoints.add(node);
    }

    // Check case 1
    if(node == 0 && childCount > 1)
        articulationPoints.add(0);
}

---

My Question: I understand why those three conditions work. However how can I convince myself that those are the only three conditions to check?

Can somebody please prove to me that those are the only three conditions and there are no other conditions to check for?

Answer 1

Here is the proof:

Given we have A -> B as an edge where A is not the root, let's assume A is an articulation point thats not the root. Removing it results in 2 subsets - the first containing the root and the second containing B.

For the subset containing B to be disjoint from the root if A is removed, B should not have a link to any node from root ... A that is it should not be able to reach a vertex higher than itself. This is possible only if:

• A -> B is a bridge meaning the highest node reachable from B is itself
• A is the only node B is connected to that is above it. This way if we remove A the highest node reachable from B is itself.