Bipartite Check, in depth

The picture

The odd-cycle theorem

The whole algorithm rests on one theorem: a graph is bipartite if and only if it contains no cycle of odd length. Both directions are short.

If the graph is bipartite, walk around any cycle. Every step crosses from one side to the other, so returning to the start takes an even number of steps. An odd cycle is therefore impossible.

Conversely, suppose there is no odd cycle. Pick any vertex r in a connected component, and colour each vertex by the parity of its shortest-path distance from r: even distances blue, odd distances red. Take any edge u-v. If u and v had the same parity, then the shortest path from r to u, the edge u-v, and the shortest path from v back to r form a closed walk of length dist(u) + dist(v) + 1, which is odd. A closed walk of odd length always contains an odd cycle, which contradicts the assumption. So every edge joins opposite colours.

That second argument is exactly what BFS computes. BFS discovers vertices in order of distance, so colouring by BFS layer is colouring by distance parity. The algorithm does not need to search for odd cycles; it builds the only colouring that could possibly work and checks every edge against it. For the general problem of colouring with more than two colours, which is NP-hard from three colours upward, see Graph Coloring, in depth.

BFS two-colouring with a certificate

The production version handles every component, works on an adjacency list, and returns either a colouring or an odd cycle. It is iterative, so deep graphs cannot overflow the call stack.

from collections import deque

def bipartite_check(n, adj):
    """n vertices 0..n-1, adj[u] = list of neighbours (undirected: both directions).
    Returns (True, colour) or (False, odd_cycle) where odd_cycle is a vertex list
    whose consecutive vertices (and last->first) are adjacent."""
    colour = [-1] * n
    parent = [-1] * n
    depth = [0] * n
    for start in range(n):
        if colour[start] != -1:
            continue                      # already coloured by an earlier component
        colour[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if colour[v] == -1:
                    colour[v] = 1 - colour[u]
                    parent[v] = u
                    depth[v] = depth[u] + 1
                    queue.append(v)
                elif colour[v] == colour[u]:
                    return False, odd_cycle(u, v, parent, depth)
    return True, colour

def odd_cycle(u, v, parent, depth):
    """u and v are adjacent with equal BFS depth; climb to their lowest common ancestor."""
    left, right = [u], [v]
    while u != v:
        u, v = parent[u], parent[v]       # equal depth, so climb in lockstep
        left.append(u)
        right.append(v)
    # left ends at the ancestor, right ends at the same ancestor: drop one copy
    return left + right[-2::-1]

Two lines carry most of the correctness. The outer for start in range(n) loop is what makes the check work on disconnected graphs; forgetting it is the most common bug, and it produces a check that silently passes graphs whose odd cycle sits in a component the search never reached. The elif colour[v] == colour[u] test is the whole decision: an edge to an already-coloured vertex is fine if the colours differ and fatal if they match.

The certificate needs one fact about BFS on undirected graphs: when a conflict is found, u and v are at the same depth. An edge between vertices whose depths differ by one gives them opposite colours, and depths can never differ by more than one across an edge. So the climb in lockstep is valid, and the cycle has length 2k + 1, where k is the distance from each endpoint to the common ancestor.

Complexity is O(V + E) time, since every vertex enters the queue once and every adjacency entry is examined once, and O(V) extra memory for the three arrays and the queue.

Worked trace

Trace the right-hand graph in the diagram, with vertices 1 to 5 and edges 1-2, 1-3, 1-4, 3-4 and 2-5. Use 1 as the start.

The conflict edge is 3-4. Both have depth 1 and parent 1, so the climb takes one step each and meets at 1. The certificate is [3, 1, 4], meaning the cycle 3, 1, 4, back to 3, of length 3. Anyone can verify this answer in a moment by checking three edges, which is the point of returning it: a bare False forces the caller to trust the code, while a certificate lets a test, a log line or a user check the claim.

Remove edge 3-4 and rerun. Every edge now joins depth 0 to depth 1 or depth 1 to depth 2, and the colouring is 1 blue, 2, 3 and 4 red, 5 blue. Either colour class can be called the left side; the split is unique per component up to swapping the colours, so a graph with c components has 2 to the power c valid two-colourings.

Variants: DFS, online edges, directed and implicit graphs

Depth-first search. DFS works as well: colour each child opposite to its parent and fail on a same-colour edge. Use an explicit stack in Python or Java, since recursion on a path graph of a million vertices exceeds default recursion limits. BFS has the slight advantage that its certificate comes out naturally from equal-depth endpoints, and in DFS you instead walk the tree path between the conflicting pair.

Edges that arrive over time. If edges stream in and you must answer after each one, rerunning BFS costs O(V + E) per edge. A union-find structure with a parity bit per node answers in near-constant amortised time. Each node stores the parity of its path to its root; uniting u and v with the constraint that they have different colours either merges two components with the right relative parity, or, if they are already in one component, checks whether their parities differ.

class ParityDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.parity = [0] * n             # parity of path to parent
        self.size = [1] * n

    def find(self, x):
        # iterative: collect the path, then compress it with accumulated parity
        path = []
        while self.parent[x] != x:
            path.append(x)
            x = self.parent[x]
        root, acc = x, 0
        for node in reversed(path):       # nearest-to-root first
            acc ^= self.parity[node]
            self.parent[node] = root
            self.parity[node] = acc
        return root

    def add_edge(self, u, v):
        """Constraint: u and v get different colours. Returns False on contradiction."""
        ru, rv = self.find(u), self.find(v)
        pu, pv = self.parity[u] if u != ru else 0, self.parity[v] if v != rv else 0
        if ru == rv:
            return pu != pv
        if self.size[ru] < self.size[rv]:
            ru, rv, pu, pv = rv, ru, pv, pu
        self.parent[rv] = ru
        self.parity[rv] = pu ^ pv ^ 1     # makes parity(u) != parity(v)
        self.size[ru] += self.size[rv]
        return True

The same structure handles mixed constraints, where some pairs must be equal and some different: use parity 0 for same and 1 for different. Edge deletions are much harder and need offline or dynamic-connectivity techniques; the details of the structure itself are in Union-Find, in depth.

Directed and implicit graphs. Bipartiteness is a property of the underlying undirected graph. If your input lists directed edges, such as 'a dislikes b', add both directions to the adjacency list or the check misses conflicts. For implicit graphs like grids, generate neighbours on the fly; a grid graph with four-way moves is always bipartite by the parity of row plus column, which makes a good sanity test.

Where it is used

Where the check earns its keep:

• Two-way partitioning with conflicts. Splitting people, services or test shards into two groups where listed pairs must be separated. The certificate tells you exactly which three, five or seven constraints are mutually unsatisfiable.
• Two-slot scheduling. Jobs that conflict cannot share a slot; with two slots this is precisely two-colouring.
• Precondition for matching. Kuhn's algorithm, Hopcroft-Karp and König's theorem all assume a bipartite graph with known sides. When the sides are not given explicitly, run the check first to obtain them, and reject the input if it fails. Kuhn's Algorithm, in depth shows the matching step.
• Consistency checks on pairwise relations. 'Opposite orientation', 'different parity' or 'complementary role' constraints from data pipelines: the parity DSU flags the first inconsistent record as it arrives.
• Graph analytics. Recommendation graphs of users and items should be bipartite by construction; an odd cycle means a data bug, such as an item ID colliding with a user ID.

Failure modes

Bugs that appear in real implementations, roughly in order of frequency:

• Only searching from vertex 0. Passes connected test cases and fails on forests and disconnected inputs.
• One-directional adjacency. Building adj[a].append(b) without adj[b].append(a) for undirected input. Conflicts are missed depending on traversal order.
• Self-loops. An edge u-u is an odd cycle of length one. The code above catches it, since colour[u] equals itself, but implementations that skip v == u to 'avoid revisiting' do not.
• Marking visited at dequeue time. Colouring a vertex when it leaves the queue instead of when it enters lets it be enqueued several times with conflicting colours, wasting time and sometimes overwriting a colour before the conflict is seen.
• Recursion depth. Recursive DFS on a long path crashes in Python around a thousand levels by default and in Java at a stack-size-dependent depth.
• Off-by-one vertex labels. Inputs numbered 1 to n with arrays sized n. Allocate n + 1 or relabel at the boundary.
• Trusting the answer without the certificate. A function that returns only True or False is hard to test. Return the colouring or the cycle and verify it.

Testing it properly

Because both outcomes come with a checkable witness, testing is unusually clean. Write a verifier and run it on random graphs.

import random

def verify(n, edges, result):
    ok, witness = result
    if ok:
        return all(witness[a] != witness[b] for a, b in edges)
    cyc = witness
    es = {frozenset(e) for e in edges} | {frozenset((a, a)) for a, b in edges if a == b}
    closed = all(frozenset((cyc[i], cyc[(i + 1) % len(cyc)])) in es for i in range(len(cyc)))
    return len(cyc) % 2 == 1 and closed

for trial in range(2000):
    n = random.randint(1, 12)
    edges = [(random.randrange(n), random.randrange(n)) for _ in range(random.randint(0, 15))]
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        if a != b:
            adj[b].append(a)
    assert verify(n, edges, bipartite_check(n, adj)), (n, edges)

The verifier never trusts the algorithm: a True answer must come with a valid colouring and a False answer with a closed odd cycle made of real edges. Random small graphs hit self-loops, isolated vertices, multiple components and parallel edges quickly. Add a few large structured cases, a million-vertex path and a large even cycle, to catch recursion and performance problems.

What to do next

1. Implement the BFS version above from memory, including the outer loop over all vertices, and run the random verifier against it.
2. Add certificate output to any existing bipartite check in your code base and log the cycle when it fails.
3. If edges arrive over time, replace repeated BFS with the parity union-find and test it against BFS on random edge sequences.
4. Solve two practice problems: splitting people into two groups given dislike pairs, and checking whether a given graph can be two-coloured.
5. Before your next matching implementation, call the check to derive the two sides instead of assuming them.
6. Read about odd cycle transversal, the problem of deleting the fewest vertices to make a graph bipartite, to see where the easy case ends.