🧠 Mental Model
A graph is bipartite if its vertices split into two sets with every edge crossing
between them — never within a set. Equivalently: you can 2-color the graph so no
edge joins same-colored vertices. The check is a traversal that colors as it goes and fails on a
conflict.
Think "two teams, every relationship is a rivalry across teams." Bipartiteness models matching,
scheduling into two shifts, and any "split into two mutually-exclusive groups" problem.
⚙️ Mechanics — 2-Coloring
- Color the start vertex (say 0). Traverse (BFS or DFS).
- Color each neighbor the opposite color.
- If you ever reach an already-colored neighbor with the same color → not bipartite.
- Repeat for every uncolored component (the graph may be disconnected).
Invariant: within a traversal, a vertex's color equals the parity of its distance
from the start. A same-color edge means two vertices at the same parity are adjacent — an odd cycle.
📐 Correctness — the Odd-Cycle Theorem
Theorem (König, 1936)
A graph is bipartite if and only if it contains no odd-length cycle.
Proof
(⇒) If bipartite with parts L, R, any cycle alternates
L, R, L, R, … and must return to its start's side — forcing an even number of
steps. So no odd cycle exists.
(⇐) Suppose no odd cycle. Run BFS from each component root, coloring by distance parity.
If some edge (u,v) joined two same-parity vertices, the tree paths to
u and v plus this edge would form a cycle of odd length
(two equal-parity path lengths + 1) — contradiction. Hence the coloring is proper and the graph is
bipartite. ∎
📊 Complexity
| Metric | Value |
|---|
| Time | O(V + E) — one traversal |
| Space | O(V) — color array + queue/stack |
💻 Reference Implementation (Java)
import java.util.*;
/** BFS 2-coloring. color[]: -1 unknown, 0/1 the two sides. */
public boolean isBipartite(List<Integer>[] adj, int n) {
int[] color = new int[n];
Arrays.fill(color, -1);
for (int s = 0; s < n; s++) { // handle disconnected graph
if (color[s] != -1) continue;
color[s] = 0;
Queue<Integer> q = new ArrayDeque<>();
q.offer(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1; // opposite color
q.offer(v);
} else if (color[v] == color[u]) {
return false; // same-color edge ⇒ odd cycle
}
}
}
}
return true;
}
🎭 Problem Variances — bipartite in disguise
The tell is "split into two groups where conflicts must be separated," or
"assign one of two states so adjacent differ."
| Disguise / phrasing | What's really asked | Twist to handle |
|---|
| "Is this graph bipartite?" | Direct 2-coloring | Handle disconnected components |
| "Possible bipartition / split people to avoid conflicts" | Build 'dislike' graph, 2-color | Edges = conflicts; check colorability |
| "Divide into two teams, rivals apart" | Same | Odd cycle ⇒ impossible |
| "Maximum matching" (bipartite) | Hungarian / Hopcroft-Karp / flow | First prove bipartite, then match (relates to Day 20) |
| "Minimum vertex cover in bipartite graph" | König's theorem | = max matching size |
| "2-SAT-ish two-state assignment" | Constraint as edges | Model 'must differ' as an edge; 2-color |
Recognition heuristic: "two mutually-exclusive groups + adjacency must cross groups" = bipartite check. If it must differ → edge; if it fails, an odd cycle is why.
⚠️ Common Pitfalls
Not looping over all components: a disconnected graph needs a color-seed per component.
Self-loops: a self-loop makes bipartiteness impossible (a vertex adjacent to itself). Guard if the input allows them.
Confusing 'unvisited' with a color: use a third sentinel (-1), not 0, for uncolored.
🎯 Problems
LC 785
Is Graph Bipartite?
Direct 2-coloring; remember disconnected components.
Med
LC 886
Possible Bipartition
Build the dislike graph, then check 2-colorability.
Med
📚 References
- CLRS, 3rd ed., §22.2 (exercises) — bipartite testing via BFS coloring.
- König, D. (1936) — Theorie der endlichen und unendlichen Graphen; the odd-cycle characterization and König's theorem.
- West, Introduction to Graph Theory, §1.2 — bipartite graphs and odd cycles.