Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?


share|cite|improve this question
@Graphth: Given the statement that Pavel wants to prove, it seems likely that bipartite in the third paragraph is a typo for non-bipartite. – Brian M. Scott Aug 24 '12 at 16:30
Sorry, indeed. Fixed. – Pavel Aug 24 '12 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 Aug 24 '12 at 18:55
@iago Yes, I think that was the intention. – Pavel Aug 24 '12 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 Aug 24 '12 at 19:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.