0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What if there were two intersecting paths $D,D'$ that intersected $C$ at different vertices? $\endgroup$ – Shubham Johri Jun 6 at 8:56
  • $\begingroup$ @Shubham You're right... I think one may be able to ammend it to account for this though? $\endgroup$ – S. Dauncey Jun 7 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.