# Proof a graph is bipartite if and only if it contains no odd cycles

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.

-

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.

-
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.

-

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.

-
I expanded your answer a bit, as it drew some low-quality flags. –  Normal Human Jul 1 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.

-