Chapter 3.4: Testing Bipartiteness

A bipartite graph is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y. Another way to think about it is that the nodes in the set X are colored red and the nodes in Y are colored blue. A graph is bipartite if it is possible to color its nodes red and blue so that every edge has one red end and one blue end.

If a graph G is bipartite, then it cannot contain an odd cycle.

First, assume a graph G is connected, since otherwise we can just compute its connected components and analyze them separately. Choose a node s in V and color it red. So all neighbors of s must be colored blue, and so on, until the entire graph is colored. Once we are done, we either have a valid coloring of G or there is some edge with 2 red or blue ends. In the latter case, G is not bipartite.

This procedure is basically BFS, coloring s red, layer 1 blue, layer 2 red, and so on. So all odd-numbered layers are blue and even-numbered layers are red. By adding a constant “color” step to the BFS implementation, the overall running time remains O(n+m).

Let G be a connected graph and let L_1,L_2,… be the layers produced by BFS starting at node s. Then exactly one of the following two things must hold:

1. There is no edge of G joining two nodes of the same layer. In this case, G is a bipartite graph in which the nodes in even-numbered layers can be colored red and the nodes in the odd-numbered layer can be colored blue.
2. There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle and so it cannot be bipartite.

Overall, I'd rate this section a 10. It was very easy to read, especially because it was so similar to our lecture.