# Number of odd cycles in non-bipartite 3-connected graph

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.

• @Graphth: Given the statement that Pavel wants to prove, it seems likely that bipartite in the third paragraph is a typo for non-bipartite. Commented Aug 24, 2012 at 16:30
• Sorry, indeed. Fixed. Commented Aug 24, 2012 at 16:31
• @Pavel I assume you admite any 4 odd cycles, because if you want they to be independent, then the 3-regular graph of 4 vertices would not satisfy the claim.
– iago
Commented Aug 24, 2012 at 18:55
• @iago Yes, I think that was the intention. Commented Aug 24, 2012 at 19:22
• @Pavel Following your idea, you can reduce the combinations of the paths to only 3 options (not too much). Decomposing the cycle in 3 odd-lenght paths you may assume that it has lenght 3 (the important is just parity). Now take $v$ at distance 1 of a vertex of the cycle. Then the only combinations you have to consider if the 2 paths to the other vertices of the cycle are odd-odd, even-even or even-odd.
– iago
Commented Aug 24, 2012 at 19:37

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}$$.