Chapter 1 · Graphs and Models
Bipartite Graphs and 2-Colouring
The odd-cycle theorem, the BFS that finds it, and why half of all "is this possible?" problems are secretly bipartite.
G is bipartite if V = A ⊔ B and every edge joins A to B. A 2-colouring is the same data: colour A red, B blue. Maximum number of edges for fixed n: |A| |B| ≤ ⌊ n2/4 ⌋, with equality at |A| = |B| — the discrete "product is maximised when the factors are equal" argument.
G is bipartite ⇔ G contains no cycle of odd length.
(⇒) On any cycle, colours must alternate, so a cycle returning to its start has even length. (⇐) Root a BFS tree at each component and put a vertex in A or B according to the parity of its distance from the root. If an edge uv joined two vertices of the same side, then dist(u) ≡ dist(v) ±od 2, and the path u ⇝ r ⇝ v plus the edge uv closes a walk of odd length; deleting cycles from that walk (cycle removal, Walks, Trails, Paths, Cycles) leaves an odd cycle — contradiction. ∎
The proof is the algorithm: one BFS per component, colour by layer parity, and the first same-parity edge you meet is an odd cycle (BFS distances give you its exact length: dist(u) + dist(v) + 1, and the two paths share a prefix, so the cycle is at most that long).
vector<int> col(n, -1);
bool bip = true;
for (int s = 0; s < n && bip; s++) if (col[s] == -1) {
queue<int> q{{s}}; col[s] = 0;
while (!q.empty() && bip) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (col[v] == -1) { col[v] = col[u] ^ 1; q.push(v); }
else if (col[v] == col[u]) { bip = false; break; }
}
}
}Colouring by DFS is equally correct (any traversal assigns consistent parities because the graph is bipartite ⟹ all paths between two fixed vertices have the same parity). But DFS does not give shortest distances, so the odd cycle you extract may not be the shortest one. For "find the shortest odd cycle" run BFS from every vertex of the graph, or use the two-BFS trick on the offending edge.
#The modelling habit
"Two groups, incompatible pairs" ⟹ bipartite graph, always. Concretely:
| statement | vertices | edges |
|---|---|---|
| "each job needs one machine, each machine one job" | jobs ∪ machines | compatibility |
| "no two conflicting items in the same box" | items | conflict ⟹ boxes = colour classes |
| "swap rows/columns so that…" | rows ∪ columns | 1-entries |
| "can you flip switches to make all lights off" | switches ∪ lights | switch affects light |
| "is this board position reachable in an even number of moves" | states | moves — parity of cycle length answers it |
A particularly olympiad-shaped use: cutting/tiling parity. A 2 × n or checkerboard tiling question is usually "the tile covers 1 black and 1 white cell, but the board has b ≠ w" — that invariant is a bipartition argument in disguise.
#Properties you get for free
If G is bipartite with parts A, B
- every subgraph and every minor is bipartite,
- χ(G) ≤ 2, and χ(G) = 2 as soon as one edge exists,
- girth ≥ 4; if additionally m = Ω(n3/2) the girth is bounded (Kővári–Sós–Turán for C4-free graphs),
- Kőnig's theorem holds: max matching size = min vertex cover size (Kőnig's Theorem and Minimum Covers),
- every edge cut has the same parity structure as the adjacency matrix M ∈ {0,1}|A| × |B| — rank arguments become available (The Matrix–Tree Theorem).
Toggle the last edge off and on: the report's 'bipartite' row flips exactly when an odd cycle appears or disappears.