Study note: This page includes worked solutions to its own exercises; attempt each exercise before opening its solution.
Deleting a connection and deleting a junction are different failures. A cycle supplies an alternative route around one of its edges, but every route may still pass through a particular vertex. The bridge criterion therefore cannot be reused unchanged to identify articulation vertices.
Rather than only produce a yes-or-no answer, we will count how many connected components remain after deleting each vertex. The count exposes the proof: some DFS child subtrees become separate pieces, while others join the part above the deleted vertex. A DFS root has no part above it, so its formula must be different.
All deletions here are individual hypothetical deletions from the same original graph. We do not delete one vertex, update the graph, and then delete another. The method is a static analysis of every possible single-vertex failure.
State exactly what is removed
Let be a finite undirected graph on vertices , allowing , self-loops and parallel edges. Deleting means removing the vertex and all of its incident edges. The remaining graph has vertices when ; an empty graph has zero connected components.
Definition 10.3.1
(Articulation by an increase in component count)
Let be the number of connected components of the original graph. For each vertex , let be the number of components of . Vertex is an articulation vertex precisely when
Deleting an isolated vertex decreases the count by one, so it is not an articulation vertex. Deleting the only vertex of a one-vertex graph leaves zero components.
Only the original component containing can split or disappear. The other components are unchanged. We will determine how many pieces replace that one component.
Concept lensStructural
Separation as a route that must pass through v
Equivalently, is an articulation vertex exactly when some two vertices are connected in yet every route between them passes through . Then and fall into different components of . The count then says how many pieces such pairs fall into.
Which DFS child subtrees can escape without their parent?
Run a DFS forest. Give each vertex a discovery time , and retain its DFS parent. A tree child is a vertex first discovered directly from the current vertex; it is not merely any adjacent vertex with a larger discovery time.
At completion of a vertex , the value is the least discovery time reachable by starting at , taking zero or more DFS-tree edges downward, then at most one non-tree edge to an ancestor; doing nothing is permitted. Initialize it to . A completed child contributes its low value, and a non-tree edge to an already discovered endpoint contributes that endpoint's discovery time. An already discovered descendant has a later discovery time and cannot lower a value that is already at most the current vertex's own discovery time.
Two structural facts make this number useful in an undirected graph. A non-tree edge joins an ancestor and a descendant, with a self-loop as a degenerate case. Also, distinct DFS child subtrees of one vertex have no edge directly between them: the first subtree to examine such an edge would discover the other endpoint before returning, placing it in the same subtree.
Theorem 10.3.2
(Separating child test at a nonroot vertex)
Let be a nonroot vertex and a tree child of . After is deleted, the subtree of is joined to the part above exactly when ; it forms a separate component exactly when
An escape that returns only to does not help after itself is removed, which is why the separating condition is non-strict.
Proof X-ray
Each qualifying child creates one separate component
The DFS-tree edges within 's subtree keep all its vertices connected after deleting . Any edge leaving that subtree must go to or an ancestor, because unrelated child subtrees have no connecting edge. If , no such edge reaches a strict ancestor of . Removing therefore leaves the entire child subtree disconnected from the rest, as one component.
If , an escape edge from the subtree reaches a strict ancestor. Combining tree paths inside the subtree with this edge connects it to the part above , without using .
For nonroot , that parent-side part is nonempty and connected by the remaining DFS-tree edges. All nonseparating child subtrees join it. Each separating child contributes one additional component and cannot join another child subtree. Thus if children satisfy the non-strict condition, the original component becomes exactly components.
Counterexample mode
Equality can protect an edge while failing to protect its endpoint
Take vertices 0, 1, 2 with one edge and two parallel edges . In a DFS rooted at 0, vertex 2 is a child of 1. The second parallel edge reaches 1, so .
Neither copy of edge is a bridge: deleting one leaves the other. But deleting vertex 1 removes both copies and edge , separating vertices 0 and 2. Vertex 1 is an articulation vertex. Using the strict bridge condition would miss it. Returning to the vertex being deleted is not a surviving escape route.
A root has child pieces but no parent-side piece
Let a DFS root have tree children. Once is deleted, each child's subtree remains connected, but different child subtrees cannot connect to one another. Those subtrees exhaust its original component apart from itself.
Proof X-ray
The root formula counts only pieces that actually exist
There is no parent-side component for a root. Its original component becomes exactly components after deletion. This includes : the root was an isolated vertex, so its component disappears. Back edges to the root are removed with it and cannot join the child pieces afterward.
The root is therefore an articulation vertex if and only if . A root with one child is not an articulation vertex, even if it has many incident edges; those edges may all enter the same DFS child subtree.
Combining the local split with the unchanged components gives the full deletion counts:
Theorem 10.3.3
(Vertex-deletion component counts)
For every vertex of , with the number of components of ,
where is the number of DFS tree children of and is the number of its tree children with .
For a nonroot, the criterion is . For a root, it is . These are consequences of the same component-count definition, rather than unrelated exceptions to memorize.
Counterexample mode
The nonroot formula invents a parent-side component at a root
A root with one tree child has one remaining piece inside its original component. In the low-link test every root child qualifies, because no vertex in its DFS tree has an earlier ancestor than the root. Blindly using would therefore return , while the correct count is .
For an isolated root the same mistaken formula returns , but the correct count is . The missing parent-side piece is exactly why the root calculation differs; checking the root's degree instead does not resolve this issue.
Common mistake
(Forgetting the unchanged components)
The formula keeps the other original components. For an isolated root in a graph with components, writing would claim that no component remains. The correct value is , as in the seven-vertex example, where deleting vertex 6 leaves one component.
Count failures in a disconnected example
Worked example 10.3.4
(Two articulation vertices and an isolated vertex have different effects)
Use and edges, in this order,
The first five vertices form two triangles sharing vertex 2, vertex 5 is attached to 4, and vertex 6 is isolated. Initially . With outer roots considered increasingly and adjacency entries kept in insertion order, the first DFS tree is the chain ; vertex 6 is the other root.
| Vertex | DFS parent | Discovery time | Low value | Components after deletion |
|---|---|---|---|---|
| 0 | none | 0 | 0 | 2 |
| 1 | 0 | 1 | 0 | 2 |
| 2 | 1 | 2 | 0 | 3 |
| 3 | 2 | 3 | 2 | 2 |
| 4 | 3 | 4 | 2 | 3 |
| 5 | 4 | 5 | 5 | 2 |
| 6 | none | 6 | 6 | 1 |
Vertex 2 has the separating child 3, since . Its deletion leaves , and . Vertex 4 has the separating child 5; its deletion leaves , and . These two vertices are the articulation vertices.
The root 0 has just one DFS child, so its deletion leaves the count at 2. Deleting isolated root 6 instead removes one whole component and reduces the count to 1. The returned count array is .
Preserve the low-link meaning in a multigraph implementation
Assign each input edge instance its own ID and store both incidences with that ID. When exploring a vertex, skip the precise edge used to reach its parent. A different parallel edge remains a non-tree edge and is allowed to contribute the parent's discovery time. A self-loop has no effect on the minimum or the number of tree children.
Duplicating an edge cannot change the vertex-deletion partition, because it adds no new reachable vertex pair. Nonetheless, retaining edge identity is necessary for the exact low values proved here and keeps the representation consistent with edge-sensitive applications such as bridges. Do not infer from the parallel-edge example that multiplicity itself creates a new articulation vertex.
Common mistake
(Skipping the parent by vertex instead of by edge ID)
If the DFS skips every edge leading back to the parent vertex, instead of only the one edge used to arrive, a parallel copy of the tree edge is ignored. In the example with edge and two copies of this gives instead of . The articulation answer is unchanged here, because both values satisfy , but the stored low value is wrong, and a bridge test built on it would report as a bridge although a parallel copy survives.
The explicit DFS stack stores a vertex and its next adjacency index. Discovery increments the parent's tree-child count. When a child frame finishes, its final low value is propagated once to the parent, and the non-strict test increments the parent's separating-child count. A root may also accumulate this latter count, but the final answer uses its tree-child count instead.
The function below assumes integer and integer endpoints in two-item edge pairs. It rejects negative and endpoints outside the vertex range. It reads edge pairs without modifying the caller's list. The result is (original_count, deletion_counts, articulation_vertices), with vertex labels in increasing order in the last list.
def vertex_deletion_components(n, edges):
if n < 0:
raise ValueError("the vertex count must be nonnegative")
graph = [[] for _ in range(n)]
for edge_id, (u, v) in enumerate(edges):
if not (0 <= u < n and 0 <= v < n):
raise ValueError("edge endpoint outside the vertex range")
graph[u].append((v, edge_id))
graph[v].append((u, edge_id))
tin = [-1] * n
low = [0] * n
parent = [-1] * n
parent_edge = [-1] * n
children = [0] * n
separating = [0] * n
timer = 0
original_count = 0
for root in range(n):
if tin[root] != -1:
continue
original_count += 1
tin[root] = low[root] = timer
timer += 1
stack = [(root, 0)]
while stack:
vertex, index = stack[-1]
if index < len(graph[vertex]):
neighbor, edge_id = graph[vertex][index]
stack[-1] = (vertex, index + 1)
if edge_id == parent_edge[vertex]:
continue
if tin[neighbor] == -1:
parent[neighbor] = vertex
parent_edge[neighbor] = edge_id
children[vertex] += 1
tin[neighbor] = low[neighbor] = timer
timer += 1
stack.append((neighbor, 0))
else:
low[vertex] = min(low[vertex], tin[neighbor])
else:
stack.pop()
predecessor = parent[vertex]
if predecessor != -1:
low[predecessor] = min(low[predecessor], low[vertex])
if low[vertex] >= tin[predecessor]:
separating[predecessor] += 1
deletion_counts = [
original_count - 1 + children[v]
if parent[v] == -1 else original_count + separating[v]
for v in range(n)
]
articulation_vertices = [
v for v in range(n) if deletion_counts[v] > original_count
]
return original_count, deletion_counts, articulation_vertices
The global count is used only after the entire forest has been explored. For with no edges, the result is (0, [], []); there are no vertices whose deletion needs consideration. Negative endpoint labels are rejected before Python could interpret them as indices from the end.
Worked example 10.3.5
(A root's graph degree does not determine its number of DFS children)
In a star with edges , , and root 0, each leaf starts a new child subtree. Deleting 0 leaves three components, so it is an articulation vertex. Each leaf deletion leaves one component.
In a triangle explored from 0 through 1, vertex 2 is discovered from 1. Root 0 has degree two but only one tree child. Its deletion leaves edge , hence one connected component. The other adjacent vertex is a descendant, not a second tree child. Count discoveries directly from the root, rather than counting all its neighbors.
Worked example 10.3.6
(A self-loop on a path changes nothing)
Take and edges . The self-loop adds two incidences to vertex 0, both examining the already discovered vertex 0, so . The DFS tree is the chain and . Vertex 2 has , so vertex 1 has one separating child and . Vertex 0 is a root with one tree child, so . Vertex 2 is not a root and has no children, so . The function returns (1, [1, 2, 1], [1]): only vertex 1 is an articulation vertex, and the self-loop plays no role.
Complexity and limits of the conclusion
With input edge instances, the adjacency representation has incidences, including two for each self-loop. Each vertex is discovered once, each incidence is examined once, and each completed child contributes constant return work. Construction, traversal and output therefore take time and additional cells. No recursion-depth limit is involved. These are standard graph-operation bounds, not bit-complexity bounds for arbitrarily large integer labels.
The final deletion counts and articulation set do not depend on DFS root or edge order, although discovery times, low values and parent arrays can change. They also do not answer failures of two vertices at once. Removing another vertex may destroy the escape path used in this proof, so single-failure answers cannot simply be combined.
The argument is for undirected connectivity. Directed strong connectivity requires a different analysis; the absence of edges between unrelated DFS subtrees used here is not a property of arbitrary directed DFS. Keep the failure object, graph type and stored low-link meaning attached to the theorem.
Exercises with complete solutions
Quick check
(1. A connected graph has nonroot vertex v with three DFS children whose low values are 2, 5, 7, while tin[v]=5. How many components remain after deleting v, and is v an articulation vertex?)
Solution · 1. Equality is a separating child too
The children with low values 5 and 7 qualify, so . The child with value 2 joins the parent-side component. With , the total is . Since this exceeds the original count, is an articulation vertex. Counting only the strict inequality would incorrectly omit the child returning only to .
Quick check
(2. A graph has c=4 components. Give D(r) for a DFS root with zero, one, or three tree children. Which of these roots are articulation vertices?)
Solution · 2. Replace exactly one original component
Use . The three answers are , and . Only the root with three children increases the count and is an articulation vertex. Zero children means an isolated root whose entire component disappears; one child leaves one replacement component.
Quick check
(3. In the seven-vertex example, list the components after deleting vertex 2 and after deleting vertex 6. Why are these independent hypothetical results?)
Solution · 3. Preserve the other original components
Deleting 2 leaves , and , so the count is 3. Deleting 6 from the original graph leaves the single component , so the count is 1. The second answer does not start from the graph with 2 already removed; each array entry refers to a separate single deletion from the unchanged original graph.
Quick check
(4. In the graph with edge 0-1 and two copies of edge 1-2, why is vertex 1 an articulation vertex even though neither copy of 1-2 is a bridge? Does adding more duplicate edges change the deletion count?)
Solution · 4. Vertex deletion removes all parallel copies at once
Deleting one copy of leaves another route between those endpoints. Deleting vertex 1 removes all its incident edges, leaving isolated vertices 0 and 2, so the count rises from one to two. More duplicate copies do not change reachable vertex pairs before or after deleting a vertex, so they do not change these counts. The extra parallel edge still matters for computing the exact low value .
Quick check
(5. A DFS root in a triangle has two neighbors but one tree child. Explain the distinction and compute the result after deleting the root. Why is degree at least two not a sufficient root test?)
Solution · 5. A descendant neighbor is not a newly discovered child
Starting along one root edge discovers the second neighbor from the first child before the root examines its other edge. Both neighbors lie in the same child subtree. Deleting the root leaves the edge connecting them, so there is one component and no articulation. Degree counts adjacent edge structure, whereas the root theorem counts separate DFS child subtrees.
Quick check
(6. Why does an iterative implementation propagate low[child] only when the child frame finishes? What goes wrong with using the initial discovery time as its final low value?)
Solution · 6. Descendant escape information arrives on return
A newly discovered child initially knows only its own discovery time. Its descendants may later find a non-tree edge to an ancestor, lowering the correct value. Propagating only that initial value can falsely declare the child separated. For example, in triangle , the non-tree edge from 2 to 0 lowers to 0. Testing the initial value against parent 1 would wrongly declare 1 an articulation vertex. The explicit frame's completion event ensures all descendant information has arrived before the parent's final test.