König's Odd-Cycle Theorem & BFS Level Parity
Why is the absence of odd cycles both necessary and sufficient for a graph to be 2-colorable? Consider running BFS from an arbitrary root $r$ in a connected component and assigning each vertex $u$ to partition $L$ if its shortest-path distance $d(r, u)$ is even, or $R$ if $d(r, u)$ is odd.
Theorem (König, 1916): An undirected graph $G = (V, E)$ is bipartite if and only if it contains no cycle of odd length.
Proof Sketch: ($Rightarrow$) Along any cycle $v_0, v_1, \dots, v_{k-1}, v_0$ in a 2-colored graph, colors must alternate $c(v_i) = i \bmod 2$. Since $v_k = v_0$, $k$ must be even.
($Leftarrow$) Suppose $G$ has no odd cycles. In each connected component, pick root $r$ and set $\text{color}(u) = d(r, u) \bmod 2$. If any edge ${u, v} \in E$ had $\text{color}(u) == \text{color}(v)$, let $w = \text{LCA}(u, v)$ in the BFS tree. Since $d(r, u) \equiv d(r, v) \pmod 2$, the paths $w \leadsto u$ and $w \leadsto v$ have the same parity, so the cycle $w \leadsto u - v \leadsto w$ has length $(d(r, u) - d(r, w)) + (d(r, v) - d(r, w)) + 1$, which is odd—a contradiction.
Constructing an Explicit Odd-Cycle Certificate
In production verification systems (such as register interference graphs or VLSI layer assignment), returning a boolean false is insufficient; engineers need the exact odd cycle causing the conflict. When BFS/DFS discovers an edge ${u, v}$ with $\text{color}[u] == \text{color}[v]$:
- Trace parent pointers $\text{parent}[u]$ and $\text{parent}[v]$ upward until they meet at their lowest common ancestor $w$ in the spanning tree.
- Concatenate the path $w \leadsto u$, the conflict edge $(u, v)$, and the reversed path $v \leadsto w$ to output a simple odd cycle in $O(V)$ time.
Step through 0-1 BFS deque relaxation (push_front for w=0, push_back for w=1), Tarjan’s undirected bridge/articulation criterion (low[v] > tin[u] / low[v] ≥ tin[u]), and Tarjan’s single-pass SCC condensation.
Invariant & State
Storing vertex colors in a std::vector<int8_t> initialized to -1 fits $64$ vertex states into a single 64-byte L1 cache line. Assigning the opposite color uses a single branchless bitwise XOR instruction: color[v] = color[u] ^ 1 (flipping $0 \leftrightarrow 1$).
Complexity Matrix
| Task | General Graph Complexity | Bipartite Graph Complexity | Algorithm Used |
|---|---|---|---|
| k-Coloring ($k = 2$ vs $k \ge 3$) | NP-Complete (k ≥ 3) | O(V + E) | BFS / DFS 2-Coloring |
| Odd Cycle Extraction | O(V + E) | O(V + E) | BFS Tree + LCA Trace |
| Maximum Independent Set | NP-Hard | O(E √V) | König's Theorem ($|V| - \text{MaxMatching}$) |
Production Implementation: Multi-Component Bipartite Verifier
#include <vector>
#include <queue>
#include <cstdint>
struct BipartiteResult {
bool isBipartite = true;
std::vector<int8_t> color; // 0 or 1 if bipartite
};
BipartiteResult checkBipartite(int n, const std::vector<std::vector<int>>& adj) {
BipartiteResult res{true, std::vector<int8_t>(n, -1)};
std::queue<int> q;
for (int start = 0; start < n; ++start) {
if (res.color[start] != -1) continue;
res.color[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (res.color[v] == -1) {
res.color[v] = res.color[u] ^ 1;
q.push(v);
} else if (res.color[v] == res.color[u]) {
res.isBipartite = false;
return res;
}
}
}
}
return res;
}Two classic bugs break bipartite checkers in production: (1) Starting BFS only from vertex $0$ instead of looping over all unvisited vertices $0 \dots V-1$, which misses odd cycles in disconnected components; and (2) forgetting that a self-loop $(u, u)$ is a cycle of length $1$ (odd), which immediately invalidates bipartiteness.