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
- 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)
- 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: