iv. Bipartite Graphs

A graph is bipartite iff it has no odd cycle iff it is 2-colourable. Test with BFS/DFS colouring per component, or online with a parity DSU. Bipartiteness unlocks the matching toolbox: König (min vertex cover = max matching), max independent set $=n-$ matching, Hall’s condition, Dilworth for posets (Bipartite Matching).

// returns colours (0/1), or an odd cycle if the graph isn't bipartite
pair<vector<int>, vector<int>> twoColour(const vector<vector<int>>& g) {
    int n = sz(g); vector<int> c(n, -1), par(n, -1), dep(n);
    for (int s = 0; s < n; s++) {
        if (c[s] >= 0) continue;
        c[s] = 0; queue<int> q; q.push(s);
        while (sz(q)) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (c[v] < 0) { c[v] = c[u] ^ 1, par[v] = u, dep[v] = dep[u] + 1, q.push(v); continue; }
                if (c[v] != c[u]) continue;
                vector<int> a{u}, b{v};                           // climb to the common ancestor
                while (a.back() != b.back()) {
                    if (dep[a.back()] >= dep[b.back()]) a.push_back(par[a.back()]); else b.push_back(par[b.back()]);
                }
                b.pop_back(); a.insert(a.end(), b.rbegin(), b.rend());
                return {{}, a};                                   // odd cycle u ... lca ... v (edge v-u closes it)
            }
        }
    }
    return {c, {}};
}

Proof: bipartite iff no odd cycle, and the extracted cycle is odd

A cycle in a bipartite graph alternates sides, so it has even length. Conversely, BFS-colour each component by depth parity. If an edge $(u,v)$ joins two vertices of the same colour, their depths have equal parity; the tree paths from $u$ and $v$ to their lowest common ancestor $w$ have lengths $d_u-d_w$ and $d_v-d_w$, of equal parity, so together with the edge $(u,v)$ they form a closed walk of odd length $d_u+d_v-2d_w+1$, which is a simple cycle because the two tree paths meet only at $w$. If no such edge exists, the colouring is proper.

Online and offline variants

• Parity DSU: each vertex stores its parity relative to its root; uniting $u,v$ requires opposite parities; an edge inside a component with equal parities creates an odd cycle. Supports “is the graph still bipartite after each added edge” in near-constant time (DSU).
• With deletions (offline): segment tree over time with a rollback parity DSU, $O(m\log m\log n)$ (CF 813F).
• Edges in a range of indices (“is the subgraph of edges $l..r$ bipartite?”): two pointers on the largest bipartite window with rollback or a link-cut tree maintaining a maximum spanning forest by deletion time; or the divide-and-conquer “minimal $r$ for each $l$” monotonicity (JOI “Joker”).

The parity / double-cover trick

To ask about walks of a given parity (“is there a walk of odd length from $s$ to $t$”, “shortest odd walk”, “reach $t$ in exactly $k$ steps for huge $k$”), BFS on the bipartite double cover: vertices $(v,p)$, edges $(u,p)\to (v,1-p)$. In a connected non-bipartite graph, every vertex is reachable with both parities; walks of length exactly $k$ exist iff the shortest walk of the right parity has length $\le k$ (pad with back-and-forth steps).

Proof: padding walks

A walk can be extended by 2 by going along any edge and back, so if a walk of length $\ell$ from $s$ to $t$ exists, so do walks of lengths $\ell +2,\ell +4,\dots$. Hence the set of achievable lengths of a given parity is exactly $\{\ell ,\ell +2,\dots \}$ where $\ell$ is the shortest walk of that parity, which is the BFS distance to $(t,\ell \mathrm{mod}2)$ in the double cover.

Where bipartite structure hides

• grids (chessboard colouring): no two adjacent cells chosen = independent set; domino placement = matching;
• rows vs columns: placing rooks, “one marked cell per row and column”;
• trees and forests (depth parity);
• even/odd sums: “no two chosen numbers sum to a prime” splits by parity (primes $>2$ are odd);
• left/right parts of a DAG path cover;
• positions vs values of a permutation.

Facts about bipartite graphs

Fact	Statement
König	max matching = min vertex cover
Gallai	max independent set + min vertex cover $=n$ (any graph)
König (edges)	min edge cover = $n$ − max matching (no isolated vertices)
Hall	a matching saturating $L$ exists iff $|N(S)|\ge |S|$ for all $S\subseteq L$
regular bipartite	every $k$-regular bipartite graph ($k\ge 1$) has a perfect matching; its edges split into $k$ perfect matchings
edge colouring	bipartite graphs are $\Delta$-edge-colourable (König’s line colouring theorem) (Colouring)
counting	perfect matchings = permanent of the biadjacency matrix: p-hard in general, $O(2^{n}n)$ by Ryser

Proofs of the matching theorems are in Bipartite Matching.

Bipartiteness is exactly the boundary between easy and hard for several of these: $k$-colouring for $k\ge 3$ is NP-complete (even restricted to planar graphs, even for $k=3$, Colouring), and general-graph matching/vertex-cover/independent-set lose their polynomial algorithms or become NP-hard outright (vertex cover and independent set; matching stays polynomial via Blossom, just slower):

Quantity	Bipartite	General
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
min-cost perfect matching	$O(V^3)$ (Hungarian)	$O(V^3)$ (weighted Blossom)

Odd cycle transversal: the minimum number of vertices to delete to make a graph bipartite. NP-hard in general, but fixed-parameter tractable in the number of vertices deleted.