prove that if $C$ and $C'$ are any two $k-cycle$ in $G$, then $C$ and $C'$ have at lease 2 vertices in common.

160 Views Asked by At

Let $k$ be the maximum length of a cycle in a non-separable graph $G$

a) prove that if $C$ and $C'$ are any two $k-cycle$ in $G$, then $C$ and $C'$ have at least 2 vertices in common.

b) Show that the result in a) cannot be improved.

Here is what I got so far.

a) Since $C$ and $C'$ are cycle, $k \geq 3$. Let $U,V$ be subset of vertices in $C$ and $C'$ respectively such that $|U|=|V|=2$. Since $G$ is non-separable, there are 2 disjoint path connecting vertices of $U$ and vertices of $V$. Now I'm stuck.