Bipartite Two-Coloring and Odd Cycles

Concept Overview

A graph is bipartite if its vertices can be divided into two disjoint and independent sets such that every edge connects a vertex in one set to a vertex in the other set. We can test if a graph is bipartite by attempting to two-color it using Breadth-First Search (BFS). If we successfully color the entire graph with two colors without any adjacent vertices sharing a color, the graph is bipartite. If we encounter a conflict (two adjacent vertices with the same color), the graph is not bipartite, and the conflict reveals an odd-length cycle, which is a mathematical proof that the graph cannot be bipartite.

Worked example: Finding an odd cycle

Consider a graph with vertices { 0, 1, 2, 3, 4 } and edges 0-1, 1-2, 2-3, 3-4, and 0-4.

We trace the deterministic BFS algorithm:

Start at vertex 0. Color it 0. Enqueue 0.
Dequeue 0. Its neighbors are 1 and 4. Color 1 with 1, color 4 with 1. Enqueue 1 and 4.
Dequeue 1. Its neighbors are 0 and 2. 0 is visited. Color 2 with 0. Enqueue 2.
Dequeue 4. Its neighbors are 0 and 3. 0 is visited. Color 3 with 0. Enqueue 3.
Dequeue 2. Its neighbors are 1 and 3. 1 is visited. Vertex 3 is already visited and has color 0. This matches the color of 2 (color 0). Conflict!

Since vertex 2 and vertex 3 have the same color, we reconstruct the cycle by traversing their parent pointers back to their Lowest Common Ancestor in the BFS tree (which is vertex 0). The cycle is 0-1-2-3-4-0. The cycle length is 5, which is odd. This odd cycle proves the graph is not bipartite.

Experimenting with the Module

You can test graphs interactively at https://riano.app/module/bipartite-two-coloring.

Enter the edges of a graph in the Edges input (e.g., 0 1;1 2;2 3;3 4;0 4).
Click Step to dequeue one vertex, scan its neighbors and reveal the resulting colors and queue.
Observe the queue, the assigned colors (blue and green), and the BFS tree structure forming as solid lines.
Alternatively, click Finish to immediately compute the terminal result.
If the graph is not bipartite, the module will highlight the odd cycle in red and display it in the results panel.
Use Reset to rewind the trace and try different graph configurations.

Limitations

This visualization is limited to exactly 5 vertices (labeled 0 to 4) to keep the layout clean and the trace readable. Real-world graphs can contain thousands or millions of vertices, but the underlying O(|V| + |E|) BFS algorithm remains the same. The algorithm assumes the input graph is undirected and simple (no self-loops or multi-edges). If the graph contains disconnected components, the algorithm correctly iterates through them in ascending numerical order, ensuring deterministic behavior.

References

Here is an external reference to learn more about the theoretical background of the algorithm:

CP-Algorithms: Bipartite Graph Check - Algorithm reference detailing BFS two-coloring and even-cycle characterization.

Bipartite Two-Coloring and Odd Cycles