Computing biconnected components

Question

My question relates to Problem 22.-2 in Introduction to Algorithms 3rd edition.

There biconnected components are defined as maximal sets of edges such that any two edges in the set lie on a common simple cycle. The problems that I am having are the last two tasks of this problem, namely

1. proving that biconnected components of a graph partition the nonbridge edges of the grap (where a nonbridge is an edge which can be omitted without disconnecting the graph)
2. computing the biconnected components.

The first task seems rather easy since one could argue that "any nonbridge has to lie on some simple cylce and is therefore in a biconnected component" and that "if two biconnected components were to share an edge they would be the same biconnected component since one can then construct a path through any pair of edges". However, here I find the second argument too unspecific: How would this path look like? How can I really argue about that since any edge on the constructed path might be in both components.

To make it clearer, a picture:

Clearly, I can construct such a simple cycle here always, but what if some red edges were also blue? Wouldn't that blow up the whole proof?

The problem I am having with (2) is of a similar nature. Before the problem definition in the book, the concept of articulation points is introduced. These are defined a vertices whose removal disconnect a previously connected graph.

Solutions I found on the internet of the "computing biconncted components"-task (such as the linear-time algorithm in https://en.wikipedia.org/wiki/Biconnected_component or 22.-2 h in https://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf) argue that "removing all articulation points respectively bridges yields the biconnected components of the graph". However, if I have the following graph

a removal of x would disconnect the graph whereas a removal of y would not. However, of the remaining graph (i.e. without x), y is an articulation point and there is no simple cycle on which e and f both lie (since y has to be visited twice in every cycle meaning it is not simple anymore). So removing articulation points alone does not suffice. The same applies to removing bridges alone with the upper graph.

How would I fix these problems?

PS:

PPS:

Answer 1

Two different biconnected components does not share an edge

Claim: Let edge $u$ lie on simple cycle $\mathcal C_u$. Let edge $v$ lie on simple cycle $\mathcal C_v$. $\mathcal C_u$ and $\mathcal C_v$ share an edge. Then $u$ and $v$ must lie on a common simple cycle.

Proof: If $v$ is on $\mathcal C_u$, we are done. So, assume $v$ is not on $\mathcal C_u$.

Let us visit the edges of $\mathcal C_v$ starting at $v$ on one direction, until we reach an edge on $\mathcal C_u$ the first time. We must be able to reach such an edge, since $\mathcal C_u$ and $\mathcal C_v$ share an edge.
Do the same on the other direction.
The edges we have visited, slightly reordered, can be seen as a path on $\mathcal C_v$: $f_{i+1}, f_i, \cdots, f_2, f_1, v, e_1, e_2, \cdots, e_j, e_{j+1}$, where

• $i\ge0$, $j\ge0$, $f_*$ and $e_*$ are edges, and
• the sequence $P_v$: $f_i, \cdots, f_2, f_1, v, e_1, e_2, \cdots, e_j$ is a a simple path on $C_v$ that is disjoint with $\mathcal C_u$ and,
• Both $f_{i+1}$ and $e_{j+1}$ are on $\mathcal C_v$ and on $\mathcal C_v$.

There are two cases.

• If $f_{i+1}$ and $e_{j+1}$ are the same edge, this is the simple case illustrated by the first graph in the question.
• Otherwise, $f_{i+1}$ and $e_{j+1}$ are different. Since both edges are on $\mathcal C_u$, there is a simple path $P_u$ on $\mathcal C_u$ from one endpoint of $f_{i+1}$, say $x$, to one endpoint of $e_{j+1}$, say $y$, that includes edge $u$.
  Let us start at edge $v$, travelling along the $f_*$ edges until we reach $x$, then travelling along the $P_u$ until we reach point $y$, then travelling along the $e_*$ edges back to edge $v$. We can verify that the edges we have thus visited is a simple cycle that contains both $u$ and $v$. (This cycle may or may not contain $f_{i+1}$. It may or may not contain $e_{j+1}$. It does contain $P_v$ and $P_u$.) $\checkmark$

The claim and its constructive proof above explains that "if two biconnected components were to share an edge they would be the same biconnected component since one can then construct a path through any pair of edges".

Two or more different biconnected components may share an articulation point

It looks like you misunderstand what you have read about "computing biconncted components".

Suppose we are given a graph $G$.

While $G$ is a disjoint union of its connected components, it is NOT necessarily a disjoint union of its biconnected components.

An articulation point of $G$ is a point that joins two or more different biconnected components ("joins" instead of "separates" is used so as to be consistent with the next statement. Either "joins" or "separates" is fine. By the way, the ordinary meaning of "articulation" means "the action or manner of jointing or interrelating"). An articulation point of $G$ belongs to each biconnected components that is directly connected to it. (Also note that a vertex of a biconnected component that is an articulation point of $G$ is not an articulation point of that biconnected component as a graph.) It does not make sense to remove any articulation point of $G$ if we want to list the vertices of each biconnected component of $G$.

We can see that "removing articulation points" is never involved when we try to find biconnected components. Articulation points serve as the shared boundary between different biconnected components, as illustrated in the following diagram from Wikipedia, where "cut vertices" are the same as "articulations points".

---

For the graph at the bottom of the question, vertex $x$ is the only articulation point. There are two biconnected components, which share vertex $x$.

• the biconnected component at the top that contains the top 2 vertices.
• the biconnected component at the bottom that contains all vertices except the topmost vertex.