MathOverflow is a question and answer site for professional mathematicians. 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

Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of fixed length

Edit: There is natural refinement of this question: what happens if the graph has boundend valence, e.g. if the bipartite graph is cubic?

share|cite|improve this question
up vote 11 down vote accepted

Finding a cycle of length 2k in an arbitrary graph is the same thing as finding a cycle of length 4k in the bipartite graph formed by subdividing every edge. So in general even cycles of fixed length are no easier to find in bipartite graphs than in arbitrary graphs. But it's possible that the lengths that are 2 mod 4 are easier to find than the lengths that are 0 mod 4, in bipartite graphs.

share|cite|improve this answer
Thanks, David! That was useful. – Tomaž Pisanski Mar 7 '10 at 5:16

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.