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.

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

How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.

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

One direction is very easy: if $G$ is bipartite with vertex sets $V_1$ and $V_2$, every step alone a walk takes you either from $V_1$ to $V_2$ or from $V_2$ to $V_1$. To end up where you started, therefore, you must take an even number of steps.

Conversely, suppose that every cycle of $G$ is even. Let $v_0$ be any vertex. For each vertex $v$ in the same component $C_0$ as $v_0$ let $d(v)$ be the length of the shortest path from $v_0$ to $v$. Color red every vertex in $C_0$ whose distance from $v_0$ is even, and color the other vertices of $C_0$ blue. Do the same for each component of $G$. Check that if $G$ had any edge between two red vertices or between two vertices, it would have an odd cycle. Thus, $G$ is bipartite, the red vertices and the blue vertices being the two parts.

share|cite|improve this answer
genius... thanks a lot Brian! – ILoveMath Nov 28 '13 at 4:58
@Atahualpa: You’re welcome! – Brian M. Scott Nov 28 '13 at 16:15

One relatively simple way is to break the if and only if into its two parts:

  • Prove that if a graph $G$ is bipartite then it has no odd cycles, and
  • If $G$ has only even cycles, then you can partition the vertices into two independent sets.

I don't think this is a named theorem, it's too simple.

share|cite|improve this answer

does this theorem have a common name?

It is sometimes called König's Theorem (1936), for example in lecture notes here.

However, this name is ambiguous.

share|cite|improve this answer
I expanded your answer a bit, as it drew some low-quality flags. – Bookend Jul 1 '15 at 17:45

(By contradiction) (->) Suppose n is odd. Let X={ui such that i is odd} and Y={ui such that i is even} as the bipartition formed in the graph. Consider cycle C=u1 u2 u3 u4...un u1 as the cycle in G. If u1 is odd, un can not be odd because there will be no bipartite formed. Therefore, n should be even.

share|cite|improve this answer

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.