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 along 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 blue vertices, it would have an odd cycle. Thus, G is bipartite, the red vertices and the blue vertices being the two parts.

Source : Link , Question Author : Asinomás , Answer Author : Brian M. Scott

Leave a Comment