Bipartite Graphs and Colouring

A graph is bipartite if its vertices split into two sets with every edge crossing between them. Equivalently — and this is the useful form:

A graph is bipartite iff it contains no odd cycle.

Testing: 2-colouring in $O(V+E)$

vector<int> color;   // -1 = uncoloured
 
bool isBipartite(int n) {
    color.assign(n, -1);
    for (int s = 0; s < n; s++) {
        if (color[s] != -1) continue;
        color[s] = 0;
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) { color[v] = color[u] ^ 1; q.push(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}

Run it per component — a graph is bipartite iff every component is.

Why bipartiteness matters

Once a graph is known bipartite, a large toolbox opens up. Most of it comes from König’s theorem, which fails on general graphs:

Quantity	Bipartite graphs	General graphs
Maximum matching	$O(E\sqrt{V})$ (Hopcroft-Karp)	$O(V^3)$ (Blossom)
Minimum vertex cover	= max matching (König)	NP-hard
Maximum independent set	$V-$ max matching	NP-hard
Minimum path cover of a DAG	$V-$ max matching	—
Chromatic number	2	NP-hard
Min-cost perfect matching	$O(V^3)$ (Hungarian)	$O(V^3)$ (weighted Blossom)

König’s theorem. In a bipartite graph, $|\text{max matching}|=|\text{min vertex cover}|$.
Hall’s theorem. A bipartite graph with parts $L,R$ has a matching saturating $L$ iff $|N(S)|\ge |S|$ for every $S\subseteq L$.
Dilworth’s theorem. In a poset, the minimum number of chains covering it equals the size of the largest antichain — computed as a bipartite matching.

Recognising a bipartite problem

Bipartiteness is often hidden. Look for a natural two-sided split:

• rows and columns of a grid,
• items and slots / people and tasks,
• vertices at even and odd depth in a tree (every tree is bipartite),
• positions of the same colour on a chessboard,
• “no two chosen cells adjacent” — an independent set in a grid graph, which is bipartite.

The classic: maximum independent set in a grid where adjacent cells conflict. Colour the grid like a chessboard, build the bipartite graph, and the answer is $V-$ max matching.

Odd cycles and generalisations

• Odd cycle transversal — the minimum vertices to delete to make a graph bipartite. NP-hard, but FPT in the number deleted.
• Bipartite DSU. To answer “would adding this edge create an odd cycle?” online, use a weighted DSU storing each vertex’s parity relative to its root. Union with parity; an edge within a component whose endpoints have equal parity closes an odd cycle.
• $k$-colouring for $k\ge 3$ is NP-complete, even for planar graphs, even for $k=3$. Bipartiteness is exactly the easy case.

// DSU with parity: find returns {root, parity}
pair<int,int> find(int v) {
    if (par[v] == v) return {v, 0};
    auto [r, p] = find(par[v]);
    par[v] = r; rel[v] ^= p;
    return {r, rel[v]};
}

See also: Bipartite Matching · Graph Fundamentals · Graph Colouring