Is a Graph Bipartite? BFS Two-Colouring and Odd Cycles

Some graph questions hide a bipartite check inside a story: split people into two teams so no rivals share a team, schedule exams in two sessions so no student has a clash, decide whether a set of "these two must differ" constraints can be satisfied. All of them ask the same thing — can the nodes be coloured with two colours so every edge joins different colours? — and all of them are answered by a BFS with one extra field per node.

The problem it solves

A graph is bipartite when its nodes split into two groups and every edge goes between the groups, never inside one. Trees are always bipartite. A square is bipartite. A triangle is not: whichever two corners you put together, the edge between them stays inside one group.

The question matters beyond puzzles. Matching problems — jobs to machines, students to projects — are usually modelled on bipartite graphs, and many algorithms assume the split is already known. Finding it, or proving that it cannot exist, is this check.

The intuition

Pick any node and give it colour 0. Its neighbours have no choice: they must be colour 1. Their neighbours must be colour 0, and so on. Each colour is forced by the one before it, which is why BFS fits: it explores the graph in rings, and colours alternate from ring to ring.

The check fails the moment an edge joins two nodes that already share a colour. When can that happen? Walk from the start node along the BFS tree to each end of that edge, then across it: you have a closed walk. Colours alternate along every tree edge, so the two ends having the same colour means the two tree paths have the same parity, and adding the edge makes a closed walk of odd length — which always contains an odd cycle. A graph is bipartite exactly when it contains no cycle of odd length.

That also gives you the certificate in both directions. If the check passes, the colouring itself is the proof. If it fails, the odd cycle is the proof.

Watch it run

The animation seats the lesson's four wedding guests at two tables. Ann goes to table 1; each of her rivals, Bob and Cy, is pushed to table 2; Dee, who feuds with both of them, lands at table 1. Every edge crosses the room, so the square is bipartite. The last frame adds one more feud, Bob against Cy — two guests already at the same table — and the split becomes impossible.

The code

The BFS version, restarted from every uncoloured node so that graphs with several components are fully checked. Nodes are numbered: 0 is Ann, 1 Bob, 2 Cy, 3 Dee.

from collections import deque

def is_bipartite(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    colour = [-1] * n                           # -1: not seated yet
    for start in range(n):                      # every component, not just node 0
        if colour[start] != -1:
            continue
        colour[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if colour[v] == -1:
                    colour[v] = 1 - colour[u]   # the opposite side
                    queue.append(v)
                elif colour[v] == colour[u]:
                    return False, None          # an edge inside one side
    return True, colour

square = [(0, 1), (0, 2), (1, 3), (2, 3)]       # ann-bob, ann-cy, bob-dee, cy-dee
print(is_bipartite(4, square))                  # (True, [0, 1, 1, 0])
print(is_bipartite(4, square + [(1, 2)]))       # (False, None)
print(is_bipartite(5, [(0, 1), (2, 3), (3, 4), (4, 2)]))   # (False, None)

The third call is the one a single BFS from node 0 gets wrong: the triangle 2-3-4 is in a separate component that a search starting at node 0 never reaches.

A second approach uses union-find, which suits edges that arrive one at a time. Give every node u a shadow u + n meaning "the other side from u". Each edge says u sits opposite v, so u joins v's shadow and v joins u's. If an edge ever connects two nodes already in the same set, they have been forced onto the same side:

def is_bipartite_uf(n, edges):
    parent = list(range(2 * n))                 # node u and its "other side" u + n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        if find(u) == find(v):                  # already forced onto the same side
            return False
        parent[find(u)] = find(v + n)           # u sits opposite v
        parent[find(v)] = find(u + n)           # v sits opposite u
    return True

print(is_bipartite_uf(4, square), is_bipartite_uf(3, [(0, 1), (1, 2), (2, 0)]))   # True False

Both are checked against the definition itself: try every one of the 2ⁿ ways to split the nodes and see whether any split has no edge inside a side. On 3,000 random graphs of up to nine nodes, including disconnected ones, BFS and union-find agree with the brute force, and every colouring BFS returns is valid:

import random
from itertools import product

def brute_force(n, edges):                      # try every one of the 2^n seatings
    return any(all(c[u] != c[v] for u, v in edges) for c in product((0, 1), repeat=n))

random.seed(12)
ok, yes = True, 0
for _ in range(3000):
    n = random.randint(1, 9)
    pairs = [(u, v) for u in range(n) for v in range(u + 1, n)]
    edges = random.sample(pairs, random.randint(0, min(len(pairs), 10)))
    truth = brute_force(n, edges)
    found, colour = is_bipartite(n, edges)
    ok &= found == truth == is_bipartite_uf(n, edges)
    if found:                                   # the colouring itself must be valid
        ok &= all(colour[u] != colour[v] for u, v in edges)
    yes += truth
print(ok, yes)                                  # True 2046

2,046 of the graphs were bipartite and 954 were not, so both answers were tested.

The complexity

BFS visits each node once and looks at each edge twice, once from each end: O(V + E) time and O(V) space for the colours and the queue. DFS works equally well; the colouring does not care about the visiting order, only that each node's colour comes from a neighbour. The union-find version runs in near-linear time with path compression, and it can answer "is it still bipartite?" after each new edge without starting over.

Where it goes wrong

• Checking one component. Starting BFS only from node 0 misses odd cycles in parts of the graph it cannot reach. Loop over all nodes, as above.
• Treating "visited" as "fine". A visited neighbour is only fine if it has the other colour. The colour comparison is the whole check.
• Self-loops. An edge from a node to itself puts both ends on the same side, so a graph with a self-loop is never bipartite. The code above handles it: the node meets itself with its own colour.
• Directed input. Bipartiteness is about the underlying undirected graph. If the input lists directed edges, add both directions before colouring.

How to say it in an interview

"I two-colour the graph with BFS. I give an uncoloured node colour 0, and every neighbour I discover gets the opposite colour of the node I came from. If I ever see an edge whose two ends already have the same colour, the graph isn't bipartite — that edge closes an odd cycle. I restart from every uncoloured node so disconnected graphs are fully checked. It's O(V + E), and if it succeeds, the colours are the two groups."

The traversal underneath is plain breadth-first search, and the union-find variant builds on disjoint sets.