# 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 $$GG$$ is bipartite with vertex sets $$V_1V_1$$ and $$V_2V_2$$, every step along a walk takes you either from $$V_1V_1$$ to $$V_2V_2$$ or from $$V_2V_2$$ to $$V_1V_1$$. To end up where you started, therefore, you must take an even number of steps.
Conversely, suppose that every cycle of $$GG$$ is even. Let $$v_0v_0$$ be any vertex. For each vertex $$vv$$ in the same component $$C_0C_0$$ as $$v_0v_0$$ let $$d(v)d(v)$$ be the length of the shortest path from $$v_0v_0$$ to $$vv$$. Color red every vertex in $$C_0C_0$$ whose distance from $$v_0v_0$$ is even, and color the other vertices of $$C_0C_0$$ blue. Do the same for each component of $$GG$$. Check that if $$GG$$ had any edge between two red vertices or between two blue vertices, it would have an odd cycle. Thus, $$GG$$ is bipartite, the red vertices and the blue vertices being the two parts.