Questions: Articulation Points and Bridges in Graphs

Question 1

A vertex v has degree 5 in a connected undirected graph. A classmate claims v must be an articulation point because removing it disconnects many edges. Which response is correct?

• A. The classmate is right — high degree means many dependencies, so removal is likely to disconnect the graph
• B. The classmate is wrong — whether v is an articulation point depends on reachability between its neighbors, not its degree
• C. The classmate is right only if all five neighbors are in different connected components
• D. The classmate is wrong — articulation points can only have degree 2 or less

Answer: (B)

Degree alone does not determine whether a vertex is an articulation point. A hub vertex with degree 5 might still leave its neighbors mutually reachable through alternative paths — it would not be an articulation point. Conversely, a degree-2 vertex connecting two otherwise separate subgraphs IS an articulation point. The critical question is: if v is removed, do its neighbors remain connected to each other? That depends on the graph's topology, not v's degree.

Question 2

In Tarjan's algorithm, vertex v has a child u in the DFS tree such that low[u] >= disc[v]. What does this tell us?

• A. The subtree rooted at u contains a back edge that reaches an ancestor of v, so v is safe
• B. The subtree rooted at u has no back edge reaching an ancestor of v, meaning removing v would disconnect u's subtree
• C. The edge (v, u) is a back edge and should be ignored in the articulation point check
• D. Vertex u is itself an articulation point

Answer: (B)

low[u] is the smallest discovery time reachable from u's subtree through any combination of tree edges and back edges. If low[u] >= disc[v], the subtree rooted at u cannot reach any ancestor of v without going through v itself. Remove v, and u's entire subtree becomes disconnected — v is an articulation point. If low[u] < disc[v], the subtree has a back edge that bypasses v, so the component stays connected without v.

Question 3

A leaf vertex (degree 1) in a connected graph is typically an articulation point.

• T. True
• F. False

Answer: False

A leaf is never an articulation point. Removing a leaf leaves the rest of the graph intact — its single neighbor simply loses one connection but remains connected to everything else. Articulation points must be internal vertices whose removal separates the graph into at least two components. The common misconception is conflating 'critical to some connections' with 'critical to graph connectivity.'

Question 4

The root of the DFS tree is an articulation point if and only if it has two or more children in the DFS tree.

• T. True
• F. False

Answer: True

The general articulation point condition (low[child] >= disc[v]) cannot be applied to the root because every vertex has a discovery time >= the root's, making the condition trivially true for all children. The root is special: its children's subtrees are only connected to each other through the root itself. If the root has one child, removing it leaves that single subtree intact. If it has two or more children, removing the root disconnects those subtrees from each other — so it is an articulation point if and only if it has >= 2 DFS children.

Question 5

Explain why the 'low value' (lowest discovery time reachable from a subtree via tree edges and back edges) is sufficient to detect articulation points without re-running DFS after each removal.

Model answer: The low value answers, in one DFS pass, the key question for every vertex: can my subtree reach above me without going through me? A back edge from a descendant to an ancestor makes that ancestor reachable without traversing the current vertex — it provides an 'escape route.' If low[child] < disc[v], child's subtree has such an escape route and v is not needed for connectivity. If low[child] >= disc[v], there is no escape route; the subtree is entirely dependent on v for connection to the rest of the graph. By computing this bottom-up during DFS, Tarjan's algorithm answers the disconnection question for every vertex simultaneously in O(V+E) time.

The insight is that back edges encode alternative connectivity. DFS already visits every edge, so tracking the minimum reachable discovery time as we go costs no extra traversals. The low value is updated upward through the DFS tree — a descendant's back edge discovery propagates to its ancestors, letting each ancestor know whether that subtree can 'escape' upward. This makes the algorithm a single augmented DFS rather than V separate DFS traversals.