# Talk:Biconnected component

WikiProject Computer science (Rated Start-class)
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start  This article has been rated as Start-Class on the project's quality scale.
WikiProject Mathematics (Rated Start-class, Mid-priority)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 Start Class
 Mid Priority
Field: Discrete mathematics

## Lowpoint

"The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if v's lowpoint is at least as large as v's depth". This is not correct.

For instance if the depth-first-search tree is like:

```    T
|
x
/ \
A   B
```

i.e, T is a tree, x is a node (not the root), A and B are subtrees.

If there is a backward edge from a node of A to a node of T, then lowpoint(x) < depth(x) so according to the previous characterization, x can not be a cut vertex. But if there is no backward edge from B to T then x is actually a cut vertex (removing x separate B from T) so the characterization is not correct.

I think it should be : "a non-root vertex x is a cut vertex iff there is no son y of x such that lowpoint(y) >= depth(x)".

In your example, depth(x) = 2 and lowpoint(A) = lowpoint(B) = 3. The terminology is a bit confusing. Bobmath (talk) 14:00, 18 May 2015 (UTC)

## Cut Vertex

IMO, it would be more appropriate for cut vertex, et al., to redirect to Connected component (graph theory). 23:55, 11 July 2010 (UTC)

## C++ example

The C++ example seems misleading and complex to me, although it directly translates the . What about a shorter recursive pseudocode like this:

```mark_lowpoint(node, parent, depth)
if not visited[node]:
if parent = root:
++root_children
visited[node] := true
min_depth_lowpoints := depth
for n in neighbours[node]
l := mark_lowpoint(node, depth+1)
if l >= depth and node != root:
articulation_point[node] := true
min_depth_lowpoints := min(l, min_depth_lowpoints)
lowpoint[node] := min_depth_lowpoints;
return lowpoint[node]

root_children := 0
articulation_point := [false, ...]
visited            := [false, ...]

mark_lowpoint(root, ..., 0)

if root_children >= 2:
articulation_point[root] := true
```