# Find all pairs of nodes whose deletion disconnects graph

Given undirected, connected graph, find all pairs of nodes (connected by an edge) whose deletion disconnects the graph. There can't be an edge connecting a node to itself.

The problem seems similar to finding articulation points of a connected, undirected graph - yet with a twist, that we have to remove a pair of vertices connected by an edge (and all other edges connected to that pair).

This is a homework question. I might not be a smart student, but neither a lazy one. I will try to answer it below, and I would love for someone to verify my understanding of the issue.

I will be basing my solution of finding Articulation Pairs (AP) based on finding articulation points by this analysis: https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ and the DFS with additional bookkeaping of 'lowpoint' value for each node, where
lowpoint(v) is a minimal depth of non-parent adjecent node at the time of traversal
found here: https://en.wikipedia.org/wiki/Biconnected_component#Algorithms

Analysis:
1) u is root of DFS tree with at least three children. Then every pair (u, child(u)) is AP.
2) u is root with at least two children, one of which (v) has at least one child. Then every pair (u, v) is AP.
3) u is not a root of DFS tree and it has a child v1 such that v1 has child v2, such that no vertex in subtree rooted with v2 has a back edge to one of the ancestors of u

Rephrasing 3):
(u,v) is AP iff:
- v is a child of u
- there exist child(v) such that lowpoint(child(v)) >= depth(u)

My questions are:
Did I miss any case? Is my reformulation of the issue sufficient for this problem?

@EDIT: This solution/analysis completely doesn't work and at this point I have no idea how to approach this issue.

• Such an edge is called "bridge" (or "isthmus", "cut-edge"). www.geeksforgeeks.org has a separate page for this problem. As you observe, the general approach is that of articulation-points. I did not verify your conclusions. – Hendrik Jan Jun 3 '18 at 23:20
• This is not a bridge problem, unfortunately. – MkjG Jun 3 '18 at 23:50
• @HendrikJan We remove not only a single edge, but two vertices -> this means an edge between them, but also every other edge connected to each of thoes vertices. – MkjG Jun 3 '18 at 23:50
• @HendrikJan Specifically, a graph represented by a circle with a single diameter line can be disconnected by removing 'diameter'-edge and two vertices connected to it. It seems like lowpoint analysis is useless in this case (all vertices in such graph would have lowpoint of zero). – MkjG Jun 4 '18 at 2:07