Prove that a finite connected graph is bipartite if and only

Prove that a finite, connected graph is bipartite if and only if it contains no cycles of odd length.

Solution

If G is bipartite with vertex sets V1 and V2, every step takes either from V1 to V2 or from V2 to V1.

Suppose that every cycle of G is even. Let v0 be any vertex. For each vertex v in the same component C0 as v0. Let d(l) be the length of the shortest path from v0 to v.

Color blue every vertex in C0 whose distance from v0 is even, and color the other vertices of C0 green. Do for each component of G. Check that if G had any edge between two blue vertices or between two vertices, it would have an odd cycle. Thus, G is bipartite,if and only if it contains no cycles of odd length