Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.