Cycle in biconnected graph

406 Views Asked by At

Suppose a graph is biconnected and has more than two vertices. Is it true that any two vertices must lie on a cycle?

My idea is: the property of being connected implies that any two vertices $a,b$ must be connected by some path. Moreover, if we remove $a$ or $b$, the graph remains connected. But I'm not sure if it implies that $a,b$ must lie on a cycle.

1

There are 1 best solutions below

2
On

As a biconnected graph is also connected, there is a path that connects two vertices A and B going through some (possibly empty) set, C, of vertices {C1, C2, C3, C4...}. From the definition of a biconnected graph, if we delete any vertex in our set C there must still be a path between A and B, hence there must be another path D, {D1, D2, D3, D4...} that does not contain any of the vertices in C (as if it did, we could delete this vertex and have no paths between A and B). Hence A and B must lie on a cycle.