Lemma: When is it possible to find a separating cycle in a biconnected graph, given a non-separating cycle?

Let \(G(V,E,\gamma)\) be a biconnected graph and let \(C(V_c,E_c)\) be a non-separating cycle with the piece \(P(V_p,E_p)\). If \(P\) is not a path, then it is possible to construct a separating cycle \(S(V_s,E_s)\), which consists of a subpath of \(C\) plus a path of \(P\) between two attachments of \(P\).

Proofs: 1

Thank you to the contributors under CC BY-SA 4.0!




  1. Di Battista G., Eades P., Tamassia R., Tollis, I.G.: "Graph Drawing - Algorithms for the Visualization of Graphs", Prentice-Hall, Inc., 1999