Problem
COM-B2-M07-P010 Bipartite Graphs Have No Odd Cycles
#10
★★★☆☆ Level 3 of 5
Prove that a bipartite graph contains no cycle of odd length.
Along a cycle the two parts must alternate.
Let the graph be split into parts \(A\) and \(B\), and every edge joins a vertex of \(A\) to a vertex of \(B\). Moving along a cycle, the vertices alternate between \(A\) and \(B\). After an odd number of steps, we would be in the other part, but to close the cycle we must return to the starting vertex and starting part. Hence the cycle length is even.
One half of the bipartiteness criterion.