# Efficient algorithm to find an vertex that is not an articulation vertex

This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201.

Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion disconnects G.

Given : Graph (undirected) $G = (V,E)$

Find : A vertex not an articulation vertex

Here is how i tried. I know a brute force way to solve the problem. A1 is the brute force algorithm given below.

Algorithm A1

1. Pick a vertex say $v$.
2. Delete the vertex temporarily from $G$ (say $G'$ is a new graph).
3. Run DFS on $G'$.
4. If graph $G'$ is connected return (V).
5. Else repeat (step 1 to step 4) for all vertice of $G$.

Runtime : $O(V(V + E))$

For better running time algorithm i tried to come up with a claim.

My Claim : A vertex is an not articulation vertex if in a DFS tree it involves in a back edge.

If the above claim is true then i only need to run the DFS algorithm once that means running time $O(V + E)$. So I have two questions 1) Is the claim correct 2) find an efficient algorithm which runs in $O(V + E)$. time.

• What do you mean with the word "involves"? – adrianN Feb 2 '17 at 8:40
• Yes but previously i assume that node u is not a root node of DFS tree – aaag Feb 2 '17 at 11:06
• @sameerkn Normally, yes. Unless there's some context that implies that a different meaning is intended. – David Richerby Feb 2 '17 at 11:21
• @sameerkn i have given an algorithm of same time complexity in the questio n .if you know an efficient algorithm please write in answer. – aaag Feb 2 '17 at 11:40
• Tarjan's algorithms grows a DFS tree. A node is not an articulation point iff it has a back edge from a subtree to a node above. Special rule for the root. – Hendrik Jan Feb 2 '17 at 11:47