Algorithm to check the 2∀-connectness property of a graph

A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of G.

I know the basic idea is to build a DFS searching tree and then check each edge is not on a circle with DFS. Any help would be appreciated.

What I expect to see is a detailed algorithm description(especially the initialization of needed variables which is obscure sometimes), complexity analysis could be omitted.

• In the literature, I think it is more common to refer to this as 2-edge connected. Jun 16 '12 at 16:39
• @utdiscant: very helpful comment. Jun 17 '12 at 22:56

A simple algorithm is the following:

Let $G = (V,E)$ be the graph you want to check for 2-connectivity.

For each edge $e = (x,y) \in E$, look if there is a path from $x$ to $y$ in $(V, E \setminus \{e\})$. If for some $e$, there is not such a path, the graph is not 2-edge connected. If there is such a path for each $e$, $G$ is 2-edge connected.

You should also note, that this algorithm is not the fastest, but very easy to understand. The path-finding part can be done using for example BFS or Dijkstra's Algorithm.

This article also shows a simple algorithm for testing 2-edge connectivity, which runs in linear time.

• You can improve this answer by outlining the algorithm given in the paper; links break.
– Raphael
Jun 17 '12 at 13:44
• It's exactly what I'm looking for, thanks! Jun 17 '12 at 22:53