3.4: Testing Bipartiteness: An Application of Breadth-first Search

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. If a graph G is bipartite, then it cannot contain an odd cycle. Note a triangle - 3 nodes all connected. The odd length cycle is 3 and therefore the graph is not bipartite.

Designing the Algorithm

Perform BFS on a graph, color the first node s red, all of layer L(1) blue, all of layer L(2) red, and so on. The total running time for the coloring algorithm is O(m+n), just as it is for BFS.

So we analyze this: 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. (i) There is no edge of G joining two nodes of the same layer. In this case G is a bipartite graph in which nodes in even-numbered layers can be colored red, and the nodes in odd-numbered layers can be colored blue. (ii) There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length, and so it cannot be bipartite.

This section defines what bipartiteness is and how to determine whether or not a graph is bipartite. 8/10.