2
$\begingroup$

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?

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If C and C' were connected with two edges, wouldn't C and C' no longer be a k-cycle (maximum length cycle)? $\endgroup$ – Luke Sep 25 '13 at 20:29
  • $\begingroup$ Why not? @Alex. $\endgroup$ – Don Larynx Sep 25 '13 at 20:35
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Sep 26 '13 at 5:37
  • $\begingroup$ "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 $\endgroup$ – Don Larynx Sep 26 '13 at 12:56
  • $\begingroup$ So? That doesn’t answer the question. $\endgroup$ – Brian M. Scott Sep 26 '13 at 12:57

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.