# Graph Theory Cycles in Nonseparable graphs

Let $k$ be the maximum length of a cycle in a nonseparable graph $G$. Prove that if $C$ and $C'$ are any two $k$-cycles in $G$, then $C$ and $C'$ have at least two vertices in common.

Nonseparable meaning biconnected. Does anyone have a hint?

Theorem. If the graph G has a vertex v that is connected to a vertex of the component G1 of G, then v is also a vertex of G1.

Suppose there exists one and only edge connecting C to C'. Removing this edge would yield two connected components.

Suppose there exists two edges connecting C to C'. Removing one edge would yield one connected component. C and C' have at least two vertices in common.

• If C and C' were connected with two edges, wouldn't C and C' no longer be a k-cycle (maximum length cycle)? – Luke Sep 25 '13 at 20:29
• Why not? @Alex. – Don Larynx Sep 25 '13 at 20:35
• Despite the acceptance, this does not answer the question. A non-separable graph is a connected graph which is not disconnected by removing a vertex. – Brian M. Scott Sep 26 '13 at 5:37
• "If the graph G has a vertex v that is connected to a vertex of the component G1 of G, then v is also a vertex of G1." @Brian M. Scott – Don Larynx Sep 26 '13 at 12:56
• So? That doesn’t answer the question. – Brian M. Scott Sep 26 '13 at 12:57