﻿ Find all edges in a graph which if removed, would disconnect a pair of vertices

# Find all edges in a graph which if removed, would disconnect a pair of vertices

I have an undirected graph G(V, E). The problem I am trying to solve is broken down into two parts:

Part 1: Given the graph, and a pair of vertices in the graph, find the edges which are contained in all paths between this pair of nodes.

Part 2: Given the graph, find all such edges such that each one is present along all paths between any two vertices in the graph.

An example for Part 2: Let the graph have nodes `{a, b, c, d, e, f, g}.` Let edges be:

``````{a, b},
{b, c},
{c, a},
{c, d},
{d, e},
{e, f}
{f, g},
{g, e}
``````

For this graph, {c, d} and {d, e} should be the edges returned.

How can you do it efficiently?

If an edge E is on a path from vertex A to vertex B, but there is also a path from A to B that does not include E, then then E is in a cycle.

If E is in a cycle, and E is on a path from A to B, then there is a path from A to B through the other edges in the cycle that does not include E.

So, the edges you are looking for in part 2 are the edges that are not in cycles that are also on a path from A to B.

1) Use the Hopcroft/Tarjan algorithm to find all the biconnected components (cycles) in the graph. See

2) Collapse each biconnected component to a single vertex (more precisely, combine any 2 vertexes connected by an edge that is in a cycle until you run out of such edges). This will create a tree corresponding to the block cut tree (also described in the above link). The component that includes A will be A in the new graph, and similarly for B.

3) Since the resulting graph is a tree, it will have only one path from A to B. Find it with DFS. The edges on that path are the answer to part 2.

4) The edges from (3), as well as the edges in every biconnected component that is adjacent to those edges, are the answer to part 1.

Yeah, it kinda sounds like @EmmanuelAC's answer was trying to point in this direction.

there is a algorithm to find "bridges", we call bridge an edge if we remove it the graph is divided in two disjoint graphs. The edges you are looking for are the bridges. How can I find bridges in an undirected graph?

Part 1. Now that you know what are the bridges, you just need to find a path between the pair of nodes and all the vertices in that path that are also bridges are the solution to part 1.

Part 2. The solution to this are all the bridges in the graph