THE BIPARTITE — a dart

THE BIPARTITE two colors, no clash — and it works iff there is no odd cycle

A graph is bipartite if its nodes split into two groups with every edge crossing between them — two colors, and no edge joins same colors. It models matchings (jobs to workers, students to schools), and it has a clean characterization: a graph is bipartite if and only if it has no odd-length cycle. You test it by 2-coloring with BFS — color the source, alternate colors outward, and if you ever try to give a node the color of a neighbor, an odd cycle exists and it is not bipartite. A 4-cycle (square) is bipartite; a triangle (3-cycle) is not — an odd loop cannot be two-colored.

THE TECHNIQUE 2-color by BFS; bipartite iff no odd cycle

The demo checks a square (an even 4-cycle, bipartite) and a triangle (an odd 3-cycle, not bipartite): live demo

HISTORY & CREDIT König · bipartite / 2-coloring

“Any graph can be split into two sides.” — only if it has no odd cycle; a triangle cannot be two-colored. cited

the test · 2-color by BFS, alternating outward; a same-color edge means not bipartite.
the characterization · bipartite iff no odd-length cycle — König’s theorem.
the examples · a square (4-cycle) two-colors; a triangle (3-cycle) cannot.

Two colors laid across a graph with no clash — possible exactly when no loop has odd length. recognizer

RECOMMEND FOR I-13 even vs odd cycle, on the compiler

On the canonical compiler, the square is a 4-edge even cycle (bipartite) and the triangle a 3-edge odd cycle (not):

$ i13 run nw_bipartite.i13 # even vs odd cycle RUN OK · 715 step(s) · peak stack 16 · call depth 5 sq_edges = 4 -- even cycle: bipartite tri_edges = 3 -- odd cycle: not bipartite square_is_even_cycle = 1 triangle_is_odd_cycle = 1

Recommend as a NULL — a recognizer. Bipartiteness is a test (can the graph be 2-colored, B41), characterized by a theorem (iff no odd cycle, B39). A keeper generates an invariant rather than checking one. NULL — the two-sided graph, and the odd cycle that forbids it.