Two-Colouring a Graph: Why BFS Decides Bipartiteness and Odd Cycles Do Not

A graph is bipartite when its vertices can be split into two sets such that every edge runs between the sets. The condition appears under many names: a scheduling problem with two incompatible resource types, a constraint system with negated equalities, a network whose nodes must alternate between two roles. Deciding it takes one traversal, and the reason it takes one traversal is a theorem about cycles that is worth knowing in both directions — not just for the algorithm but for the failure cases it exposes.

The colouring invariant

Fix a starting vertex and give it colour 0. Every neighbour must then receive colour 1, every neighbour of those colour 0, and so on. A traversal that assigns colours as it discovers vertices either completes with every edge joining opposite colours, or finds an edge whose endpoints share a colour. There is no third outcome, and the search need not backtrack: the colour of a vertex is forced by the first path that reaches it.

from collections import deque

def two_colour(adj):
    n = len(adj)
    colour = [-1] * n
    for s in range(n):
        if colour[s] != -1:
            continue
        colour[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if colour[v] == -1:
                    colour[v] = colour[u] ^ 1
                    q.append(v)
                elif colour[v] == colour[u]:
                    return False, (u, v)   # conflict edge
    return True, None

The outer loop is necessary for disconnected graphs; the algorithm is per component, and a graph is bipartite exactly when every component is. The conflict returned is an edge joining same-coloured vertices, which is the witness that no valid colouring exists. The total work is Θ(n + m), the same as a plain traversal, because each vertex is coloured once and each edge is inspected from both ends.

Breadth-first order is not required for correctness — a depth-first search with the same rule decides the same question in the same time. It is convenient because the colour of a vertex in BFS equals its distance parity from the source, which makes the conflict edge easy to interpret: it joins two vertices at the same distance from the source, closing an odd cycle.

The odd cycle equivalence

The theorem is: a graph is bipartite if and only if it contains no cycle of odd length.

One direction is immediate. Colour the vertices of an odd cycle alternately around the cycle; after an odd number of steps the alternation returns to the start with the wrong colour, so no two-colouring of the cycle exists, and a graph containing it cannot be two-coloured either.

The other direction is constructive and is what the traversal realizes. Suppose a colouring attempt fails at an edge (u, v) with equal colours. Both u and v were reached from the same source, and in the BFS tree their distances have the same parity. The tree paths from the source to u and to v, together with the edge (u, v), form a closed walk of length dist(u) + dist(v) + 1. The two tree paths share a prefix up to their lowest common ancestor; removing the shared prefix leaves a closed walk that starts and ends at the ancestor, has odd length because the two remaining path lengths have equal parity plus the one edge, and therefore contains an odd cycle. The conflict edge is thus a certificate, not just a symptom.

This equivalence is why the test is exact and linear. It is also why the test cannot be extended by local reasoning to related questions. Three-colouring has no such characterization: deciding whether a graph is 3-colourable is NP-complete, and no traversal assigns forced colours because a vertex’s colour is not determined by its neighbours’ colours when three are available.

What a conflict edge tells you

The returned edge is useful beyond a boolean. Its endpoints lie in the same BFS layer, and an odd cycle can be extracted by walking both parent chains to their meeting point and closing the walk with the conflict edge. The cycle produced is simple, has odd length, and is contained in the union of the two tree paths plus that edge. It is not necessarily the graph’s shortest odd cycle — finding the odd girth needs more than one traversal — and it is not necessarily the shortest odd cycle through the conflict edge, because the BFS tree is rooted at an arbitrary source rather than at one of the edge’s endpoints.

For constraint systems the conflict is a proof of inconsistency. If each edge means “these two variables must differ”, then a set of constraints is satisfiable exactly when the constraint graph is bipartite, and the conflict edge names a subset of constraints that cannot all hold. Enumerating that subset — the odd cycle — is the minimal unsatisfiable core for this constraint language, which is why solvers that handle difference constraints report cycles rather than merely reporting failure.

The witness also survives incremental use. Adding an edge to a bipartite graph preserves bipartiteness only if the new edge joins opposite colours in the existing colouring; if it joins same-coloured vertices, it creates an odd cycle through that edge and through the tree paths. Deleting an edge can restore bipartiteness only if the deleted edge lay on every odd cycle, which is a stronger condition than being a bridge and requires knowing the cycle structure, not just the colours.

Non-bipartite inputs and the cost of the check

Self-loops make a graph non-bipartite immediately: an edge from a vertex to itself joins a vertex to itself, and the two required colours coincide. Parallel edges between the same pair are harmless — they duplicate a constraint that is already satisfied. Implementations that treat a self-loop as an ordinary edge and skip it because the target is already coloured will report a bipartite result for a graph that has none, so the self-loop case must be checked explicitly, or the colour comparison must be performed for every edge including those whose target is already visited.

Disconnected graphs need the loop over components, and isolated vertices are trivially bipartite and may be assigned either colour. A graph with no edges is bipartite and its colouring is arbitrary; the algorithm above assigns every isolated vertex colour 0, which is a valid colouring and also the one that makes later code uniform.

The check is a decision procedure, not a construction. It answers whether a colouring exists and produces one, but it does not produce the colouring that optimizes anything — minimum number of vertices of one colour, balanced partition, or maximum cut. Maximum bipartite subgraph is NP-hard, and the traversal’s arbitrary colouring can be far from optimal: on an odd cycle of length 2k+1 the algorithm fails outright, while deleting a single edge yields a bipartite graph with a partition of sizes k and k+1. Recovering that partition from a failed colouring requires searching over which edge to delete.

Relationship to matching and to other decompositions

Bipartiteness is the precondition for the classical augmenting-path algorithms for maximum matching, which alternate between matched and unmatched edges along paths and therefore require the graph to have no odd cycles. On a general graph the same problem needs the blossom contraction that handles odd cycles explicitly, and the contrast between the two algorithms is the clearest illustration of what the bipartite restriction buys: a linear-time structural test that removes an entire class of difficult cases.

The test also underlies the standard reduction from 2-satisfiability to reachability. A 2-CNF formula becomes an implication graph on twice as many vertices as variables, and the formula is satisfiable exactly when no variable shares a strongly connected component with its negation. That is a different decomposition of a different graph, and the two are often confused because both are described as “checking consistency with a traversal”; the bipartite test works on the constraint graph and detects odd cycles, while the 2-SAT test works on the implication graph and detects mutual reachability.

One further structural connection: a graph is bipartite exactly when its adjacency matrix can be permuted into block off-diagonal form. That is the same statement as the colouring, expressed in linear algebra, and it is the form in which the property surfaces in spectral partitioning and in the analysis of Markov chains that alternate between two state classes. The permutation is precisely the colouring, and the traversal computes it in linear time without touching the matrix.

The limiting case for the whole family is the cycle test on undirected graphs described in the edge classification material: bipartiteness asks for the parity of cycles, while acyclicity asks for their existence. Both are answered by a single pass with the right bookkeeping, and neither generalizes to counting cycles, which is where the linear-time guarantees end.