Chapter 3.4

Testing Bipartiteness: An Application of Breadth-First Search

A bipartite graph is a graph where one node V can be partitioned into sets X and Y where X are red and Y are blue. In a bipartite graph it is possible to color all the nodes blue and red so every edge has one red end and one blue end.

(3.14) A graph is not bipartite if it contains an odd-length cycle.

How can we test for bipartiteness?

The Algorithm:

• Assume the graph is connected
• pick any node s in V and color it red
• color all neighbors of S blue
• color all of their neighbors red and so on until the graph is completely colored

The algorithm design is identical to BFS as we are moving outward from s (color odd layers blue and even layers red) The total running time is O(m+n)

(3.15) Algorithm

Let G be a connected graph, and let L₁, L₂,… 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 odd-numbered layers 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.