Let G V E be a loopfree undirected graph Prove that if G co

Let G = (V, E) be a loop-free undirected graph.

Prove that if G contains no cycle of odd length, then G is bipartite.

15. Let G = (V, E) be a loop-free undirected graph. Prove that if G contains no cycle of odd length, then

Solution

Answer :

Suppose G has no cycles of odd length. We may assume that G is connected (otherwise we consider the connected components of G ).

Pick a vertex u₀ V . For every vertex v V , let p_i be any path from u₀ to v , and let d_v be its length.

Set L = { v V / d_v is even } and let R = { v V / d_v is odd } .

Clearly V = LUR is a partition of V. We now show that ( L; R; E ) is bipartite.

If not, then there is some { u , v } E such that both u , v L or both u,v R .

In either case, there is a closed walk in G given by p_u , { u,v } , p_v (from u₀ to u , then u to v , then v to u₀ ),

whose total length is d_u + d_v + 1, which is odd. Since G has a closed walk of odd length, then G also has a

cycle of odd length . This is a contradiction to our assumption that G has no cycles of odd length. Thus G = ( L; R; E ) is bipartite