Bipartite Two-Coloring and Odd Cycles

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.

Experimenting with the Module

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

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