[Math] Number of odd cycles in non-bipartite 3-connected graph

graph theory

By going over the tests of previous years in graph theory, I've come across an interesting (in my opinion) question:

$G$ is 3-connected, non-bipartite graph. Prove that $G$ contains at least 4 odd cycles.

I tried the following way: as $G$ is non-bipartite, it has an odd cycle $C$. Now, since $G$ 3-connected, there should be $v \in V(G-C)$ with 3 paths to $C$. From here it should be a game of combining odd/even paths, to get what is needed. But there are too much options.

Is there any other way?

Thanks.

Best Answer

Your idea is correct and doesn't have that many cases, you can simplify it quite a bit. Let $C$ be an odd cycle in $G$ of minimum length, this assures that $C$ isn't hamiltonian and there is a vertex $v\in V(G)\setminus V(C)$. As you said, there are 3 disjoint paths $t_1$, $t_2$ and $t_3$ between $v$ and $C$. Call $x_i$ the extreme of $t_i$ in $C$. Observe that for $i\neq j$, there are two $x_ix_j$-paths contained in $C$, one of even length and one of odd length. Define the cycle $C_{i,j}$ as follows:

  1. If the sum of the lengths of $t_i$ and $t_j$ is even, the cycle starts in $v$, follows $t_i$, then the odd $x_ix_j$-path in $C$ and finally it follows $t_j$.
  2. If the sum of the lengths of $t_i$ and $t_j$ is odd, do the same but use the even $x_ix_j$-path in $C$.

Hence, the four odd cycles are $C$, $C_{1,2}$, $C_{1,3}$ and $C_{2,3}$.

Related Question