# 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. – utdiscant Jun 16 '12 at 16:39
• @utdiscant: very helpful comment. – caozhu Jun 17 '12 at 22:56

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.