---
title: "Bipartite Graphs and 2-Colouring"
summary: The odd-cycle theorem, the BFS that finds it, and why half of all "is this possible?" problems are secretly bipartite.
difficulty: core
tags: [colouring, parity, matching]
time: n + m
space: n
prereq: [foundations/representation, trees/bfs]
see: [matching/bipartite, special/twosat]
---

:::definition label="Bipartite"
$G$ is **bipartite** if $V = A \sqcup 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| \le \lfloor n^2/4 \rfloor$, with equality at $|A| = |B|$ — the discrete "product is maximised when the factors are equal" argument.
:::

:::theorem title="The one-characterisation"
$G$ is bipartite $\iff$ $G$ contains no cycle of odd length.
:::

:::proof
$(\Rightarrow)$ On any cycle, colours must alternate, so a cycle returning to its start has even length.
$(\Leftarrow)$ 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 $\operatorname{dist}(u) \equiv \operatorname{dist}(v) \pmod 2$, and the path $u \leadsto r \leadsto v$ plus the edge $uv$ closes a walk of odd length; deleting cycles from that walk (cycle removal, @foundations/walks) 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: $\operatorname{dist}(u) + \operatorname{dist}(v) + 1$, and the two paths share a prefix, so the cycle is at most that long).

```cpp bipartite.cpp
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; }
        }
    }
}
```

:::note title="DFS works too — with one caveat"
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 \times n$ or checkerboard tiling question is usually "the tile covers 1 black and 1 white cell, but the board has $b \ne w$" — that invariant is a bipartition argument in disguise.

## Properties you get for free
:::props title="If G is bipartite with parts A, B"
- every subgraph and every minor is bipartite,
- $\chi(G) \le 2$, and $\chi(G) = 2$ as soon as one edge exists,
- girth $\ge 4$; if additionally $m = \Omega(n^{3/2})$ the girth is bounded (Kővári–Sós–Turán for $C_4$-free graphs),
- Kőnig's theorem holds: max matching size = min vertex cover size (@matching/konig),
- every edge cut has the same parity structure as the adjacency matrix $M \in \{0,1\}^{|A| \times |B|}$ — rank arguments become available (@matrices/matrix-tree).
:::

:::demo id="graph-explorer" caption="Toggle the last edge off and on: the report's 'bipartite' row flips exactly when an odd cycle appears or disappears."
:::

:::problems
- [[CSES 1668]] Building Teams | https://cses.fi/problemset/task/1668 | easy | 2-colouring
- [[SPOJ BUGLIFE]] Buggy… love | https://www.spoj.com/problems/BUGLIFE/ | easy | 2-colouring
- [[CF 1338B]] Edge Weight Assignment | https://codeforces.com/problemset/problem/1338/B | hard | parity of paths between leaves, one DFS
- [[CSES 2179]] Even Outdegree Edges | https://cses.fi/problemset/task/2179 | hard | parity, matching
:::