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?


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.