Bipartite Graphs and Two-Coloring

Intuition

A graph is bipartite if its vertices can be split into two sides so that every edge goes from one side to the other, never within a side. Workers and jobs, students and classes, and any grid (color it like a chessboard) are natural examples. Trees are bipartite too: color by depth parity.

Three statements are equivalent:

1. The graph is bipartite.
2. The vertices can be colored with two colors so that every edge joins different colors.
3. The graph has no cycle of odd length.

The proof is also the algorithm. Pick an uncolored vertex, give it color 0, and traverse: every neighbor of a color-0 vertex must be 1, every neighbor of a color-1 vertex must be 0. Inside one component the color of a vertex is forced to be the parity of its distance from the start. If some edge joins two vertices of the same color, the two tree paths to it plus that edge form an odd cycle, so no coloring can exist. If no such edge appears, you have built a valid coloring.

When to use it in interviews / OAs

• "Split people into two groups so that everyone who dislikes each other is separated" (possible bipartition).
• "Is this graph bipartite?" asked directly, or disguised as "two teams", "two time slots", "two rooms" with conflicts.
• Odd-cycle detection in an undirected graph.
• As a first step before bipartite matching, minimum vertex cover or maximum independent set, which are easy on bipartite graphs but hard in general.
• Grid parity arguments: on a chessboard coloring, every move to an adjacent cell switches color, which bounds tilings and reachability.

Template

BFS two-coloring

from collections import deque


def two_color(n: int, adj: list[list[int]]) -> list[int] | None:
    # returns a color (0/1) per vertex, or None if the graph has an odd cycle
    color = [-1] * n
    for s in range(n):  # one BFS per component
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return None  # same color on both ends: odd cycle
    return color


def possible_bipartition(n: int, dislikes: list[tuple[int, int]]) -> bool:
    adj: list[list[int]] = [[] for _ in range(n + 1)]  # people are labeled 1..n
    for a, b in dislikes:
        adj[a].append(b)
        adj[b].append(a)
    return two_color(n + 1, adj) is not None

Parity union-find: edges arriving one at a time

If edges are added online ("after which edge does the graph stop being bipartite?"), rerunning BFS is too slow. Store, for every vertex, whether its color equals its parent's color in a union-find tree; the color relative to the root is the XOR along the path.

class ParityDSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.parity = [0] * n  # 1 if x's color differs from parent[x]'s color

    def find(self, x: int) -> tuple[int, int]:
        # returns (root, color of x relative to the root)
        path = []
        while self.parent[x] != x:
            path.append(x)
            x = self.parent[x]
        acc = 0
        for node in reversed(path):  # nodes nearest the root first
            acc ^= self.parity[node]
            self.parity[node] = acc
            self.parent[node] = x  # path compression
        return x, (self.parity[path[0]] if path else 0)

    def add_edge(self, u: int, v: int) -> bool:
        # demand color(u) != color(v); False means this edge closes an odd cycle
        ru, pu = self.find(u)
        rv, pv = self.find(v)
        if ru == rv:
            return pu != pv
        self.parent[ru] = rv
        self.parity[ru] = pu ^ pv ^ 1  # chosen so that u and v end up different
        return True

Complexity

BFS (or DFS) coloring is O(n + m) time and O(n) extra space. The parity union-find costs amortized O(log n) per edge with path compression alone (add union by size for near-constant time).

Common pitfalls

• Only coloring from vertex 0. A disconnected graph needs one traversal per component; an isolated odd cycle elsewhere would be missed.
• Self-loops. An edge (v, v) is an odd cycle of length 1, so the graph is not bipartite. The BFS above catches it (color[v] == color[u]).
• Directed input. Bipartiteness ignores direction; add both directions before coloring.
• 1-indexed labels. Allocate n + 1 slots, as in possible_bipartition, or vertex n silently falls off the end.
• Recursive DFS coloring on a long path can exceed Python's recursion limit; BFS avoids the issue.
• Assuming the coloring is unique. Each component can flip its colors independently, so there are 2^c valid colorings for c components. If the question asks for the largest side, choose per component.

Interview variations

• Possible bipartition / is graph bipartite. The template, applied directly.
• Maximize the number of groups where adjacent vertices must be in consecutive groups: each component must be bipartite; then the best group count for that component is the maximum number of BFS layers over all starting vertices, and the answer adds up over components.
• Bipartite matching. Many assignment questions (workers to jobs, students to seats) become maximum matching on a bipartite graph; König's theorem then gives minimum vertex cover = maximum matching.
• Grid coloring. Adjacent cells always differ in (r + c) % 2; this is why a board with two opposite corners removed cannot be tiled by dominoes.
• Online conflicts. "Process pairs of rivals; report the first pair that makes a two-team split impossible": parity union-find.