# 2-Edge Connectivity in a Graph

Given a undirected connected graph, check if the graph is 2-edge connected or not.

A connected graph is 2-edge-connected if it remains connected whenever any edges is removed. A bridge or cut arc is an edge of a graph whose deletion increases its number of connected components. i.e. whose removal disconnects the graph. So if any such bridge exists, the graph is not 2-edge-connected.

For example,

Below graph has 6 vertices and 3 bridges (highlighted in red) Prerequisite:

A simple approach is to remove each edge from the graph one by one and run DFS or BFS starting from any vertex. If the DFS or BFS covers all nodes in the graph, then the removed edge cannot be a bridge. If not, that edge is bridge. The time complexity of above solution is O(E(V + E)) where V is number of vertices and E is number of edges in the graph.

We can solve this problem efficiently in one pass of DFS. When we do a DFS from vertex v in an undirected graph, there could be edges which are going out of the sub tree i.e back edges. We can say that the graph is 2-edge connected if and only if for every edge u->v in the graph, there is at-least one back-edge that is going out of subtree rooted at v to some ancestor of u. When we say subtree rooted at v, we mean all v’s descendants including the vertex itself.

In other words, when we backtrack from a vertex v, we need to ensure that there is some back-edge from some descendant of v (including v) to some proper ancestor(parent or above) of v.

How should we modify DFS so that we can check if there is a back-edge going out of every sub tree?

We can modify DFS such that `DFS(v)` returns the smallest arrival time to which there is an back edge from the sub tree rooted at v. For example, let arrival(v) be the arrival time of vertex v in the DFS. Then if there is a back out of the sub tree rooted at v, it’s to something visited before v & therefore with a smaller arrival value. Remember for a back edge `u -> v` in a graph,

arrival[u] > arrival[v]

Suppose there are four edges going out of sub-tree rooted at v to vertex a, b, c and d and with arrival time A(a), A(b), A(c) and A(d) respectively. We look at their four arrival times & consider the smallest among them and that will be the value returned by DFS(v). i.e. DFS(v) returns min of A(a), A(b), A(c) and A(d). But before returning, we have to check that min (A(a), A(b), A(c), A(d)) is less than the A(v). If min(A(a), A(b), A(c), A(d)) is less than the A(v), then that means that at-least one back-edge is going out of the sub tree rooted at v. If not, we can say that (parent[v], v) is a bridge.

Output:

2, 1
3, 5
0, 2

## Java

Output:

2, 1
3, 5
0, 2

Please note that the same edges might end up printed twice. We can use a std::map avoid that with key as vertex number and value as std::set. i.e. std::map<int, set<int>>.

The time complexity of above solution is O(n + m) where n is number of vertices and m is number of edges in the graph.

Image credits: http://mathworld.wolfram.com/GraphBridge.html     (3 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest  