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) Claim 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.

The Proof

Consider case 1 where there is no edge joining two nodes of the same layer by theorem 3.4 we know every edge of G joins nodes in either the same or adjacent layer. In this case we assume they never join in the same layer, so every edge joins two nodes in adjacent layers. Because the coloring gives nodes in adjacent layers opposite colors, we know every edge has ends with opposite colors and the graph is bipartite.

Consider case 2 where G must contain an odd cycle so there is an edge that connects two nodes in the same layer.