Question bank — Articulation points and bridges — Tarjan's low-link values

True — an edge is a bridge exactly when it lies on no cycle; if any cycle passes through it, that cycle is an alternate route, so removing the edge keeps the graph connected.

False — an endpoint of degree 1 (a leaf) is not a cut vertex, because removing it disconnects nothing new. E.g. in 0—1 the edge is a bridge but neither vertex is an articulation point (each has only one neighbour).

False — a "bowtie" (two triangles sharing one vertex) has zero bridges but the shared vertex is an articulation point. Bridge-free ≠ cut-vertex-free.

True — a bridge $(u,v)$ with both endpoints of degree $\ge 2$ forces at least one endpoint to be a cut vertex; and a degree-1 endpoint makes the other endpoint a cut vertex (if it has other neighbours). A graph with $\ge 3$ vertices and a bridge always has a cut vertex.

False — the root has no ancestor, so that inequality is always true for every child. The correct root rule is a separate case: ==$\ge 2$ DFS-tree children==.

False — undirected DFS produces only tree edges and back edges; there are no forward or cross edges, because the first time you see the other endpoint you'd have already taken it as a tree edge.

False — $\text{low}[u]$ starts at $\text{disc}[u]$ and only ever takes a $\min$, so $\text{low}[u]\le \text{disc}[u]$ always.

False — take two triangles joined by a path; several vertices sit on cycles yet are still cut vertices because they gate access to separate blocks. Being on a cycle only protects the edges of that cycle.

True — a single edge can create cycles that give many subtrees a back-route above their gateway vertices, lowering their $\text{low}$ values and erasing multiple cut vertices simultaneously.

True — a tree has no cycles, so no edge has an alternate path; removing any edge splits the tree into two components.

Wrong — a back edge is not a tree edge, so we record only how high we jumped, which is $\text{disc}[w]$, not $\text{low}[w]$. Using $\text{low}[w]$ double-counts paths through $w$'s subtree and can wrongly lower $\text{low}[u]$, hiding real bridges.

Wrong sign — bridges need the strict $>$. Equality means a back edge reaches $u$ itself, giving an alternate route around the edge $(u,v)$, so it is not a bridge. (Articulation uses $\ge$ because deleting the vertex $u$ kills even that back edge.)

Wrong with multi-edges — if two parallel edges join $u$ and its parent, the vertex-based skip discards the second edge, which is a genuine back-route, and you'd falsely report a bridge. Track the edge id and skip the parent edge exactly once.

Wrong if the graph is disconnected — you must loop over every vertex and start a fresh DFS on each undiscovered one, otherwise components never touched by the DFS from 0 are silently ignored.

Wrong — degree $\ge 2$ is necessary but nowhere near sufficient. Any interior vertex of a cycle has degree 2 yet is not a cut vertex. What matters is whether some child subtree cannot escape above $u$.

Wrong — the tests compare the child's escape height $\text{low}[v]$ against the parent's own discovery time $\text{disc}[u]$, asking "can $v$'s subtree reach $u$ or above?" Comparing to $\text{low}[u]$ mixes in $u$'s own back edges and breaks the logic.

Wrong order — $\text{low}[v]$ is only finalized after $v$'s whole subtree is explored, so the update must come after the recursive call returns; before the call $\text{low}[v]$ is just its own $\text{disc}$.

A tree child's entire subtree legitimately belongs to $u$'s reachable set, so we inherit its best escape $\text{low}[v]$; a back edge is a single one-time jump whose only information is the height it lands at, $\text{disc}[w]$.

The root has no ancestor to reach "above," so $\text{low}[v]\ge \text{disc}[\text{root}]$ holds trivially for every child; the meaningful question becomes whether $\ge 2$ independent subtrees hang off it, since they can only interconnect through the root.

Deleting an edge leaves $u$ present, so a back edge to $u$ ($\text{low}[v]=\text{disc}[u]$) is a valid detour → not a bridge. Deleting the vertex $u$ destroys that back edge too, so even equality still severs the subtree → still a cut vertex.

Each vertex is discovered once and each edge examined a constant number of times while computing $\text{disc}$ and $\text{low}$; the bridge/AP tests are $O(1)$ checks folded into that same traversal — no extra pass needed. See Big-O Notation.

That back edge is an alternate path connecting the subtree to an ancestor, so removing the tree edge no longer disconnects anything — the graph stays in one piece through the back edge.

The parent edge is the tree edge we descended on — reusing it gives no new "climb up" information. Every other visited neighbour is a genuine ancestor reachable by a real back edge, which is exactly the escape route $\text{low}$ must capture.

Their removal increases the number of connected components, meaning the network splits — a single edge or single vertex whose loss disconnects the graph, the graph-theory analogue of a critical cable or a critical router.

Neither — with no edges there is nothing to remove and removing the lone vertex still leaves zero components in the remaining graph, so it's not a cut vertex.

The edge is a bridge (removing it disconnects the two vertices), but neither endpoint is an articulation point, since each has degree 1 and removing a leaf disconnects nobody new.

Zero of each — every vertex and edge lies on the cycle, so each node has an alternate route around it and no single removal splits the graph.

Yes, provided the outer loop restarts DFS on each undiscovered vertex; bridges and articulation points are computed within each component independently, and cross-component absence of edges never confuses the tests.

A self-loop is never a bridge and creates no articulation point; it should be ignored (or treated as a back edge to $u$ itself giving $\text{disc}[u]$, which changes nothing since $\text{low}[u]$ already equals $\text{disc}[u]$).

No — each edge is a backup for the other, so removing one leaves the graph connected; the naive v == parent skip must not treat the second edge as absent, or it will falsely flag a bridge.

All edges are bridges (no cycles anywhere), and every interior vertex (1, 2, 3) is an articulation point; the two endpoints (0 and 4) are leaves and are not cut vertices.