Lesson 5

It turns out that the existence of an odd-length cycle is the only obstacle to bipartiteness.

Theorem. A graph is bipartite if and only if it contains no odd-length cycles.

Proof. One direction is simple: if the graph has an odd-length cycle, even that cycle can't be colored with two colors.

Now show that if there are no odd-length cycles, then the graph can be properly colored with two colors. Without loss of generality, assume the graph is connected: if it has multiple connected components, bipartiteness can be checked independently for each.

Use the following natural algorithm. Fix any vertex \(s\) and color it red. This is step one. In step two, color all neighbors of \(s\) blue. In step three, color red all neighbors of the vertices colored blue in step two. And so on. As seen, on odd steps we use red, and on even steps blue. If we try to color a vertex already colored, we just overwrite its old color.

Since the graph is connected, all vertices will be colored. It remains to show the coloring is proper. Suppose not, and there is an edge \(\{u,v\}\) with both \(u\) and \(v\) colored, say, blue. Then both got colored on even steps. This implies the existence of two paths from \(s\) to \(u\) and \(v\) of odd lengths. Combining these with edge \(\{u,v\}\) gives an odd cycle (possibly with repeated vertices and edges, which can be removed to get a simple odd cycle).◼