Finding pairs of vertices which would disconnect a graph

Question

An assignment question asks,

Given a connected, undirected graph $G$, describe an algorithm which can determine if the removal of any pair of vertices would cause $G$ to become disconnected.

There is an obvious brute force solution, which is to just generate all pairs of vertices, produce new graphs with those vertices removed, and then test if that graph is connected using something like a BFS, running in $O(|V|^3)$ time.

However, I feel like this is not the intent of the question. We learned about an algorithm to find the articulation points of a graph, and it seems like something like this should be possible to determine if the removal of any pair of vertices would disconnect the graph, but I am not sure how it would be applicable.

Answer 1

Assume that $G=(V,E)$ does contain any articulation point (otherwise the answer is easy).

One simple approach that requires $O(|V| \cdot |E|)$ time is that of computing the articulation points of $G-v$ for each $v \in V$.

If you find any articulation point $u$ then removing the two of vertices $\{u,v\}$ disconnects the graph.

In practice this amounts to running the depth first search needed to compute the articulation points of $G-v$ on $G$, while ignoring the edges to $v$.