Bipartite graphs (2-colouring)

You’ll recognise it when

• You must split people, tasks or nodes into two groups so that no two “enemies” end up in the same group.
• The question says “2-colour”, “two teams”, “two sides” or “alternate” and gives you pairs that must differ.
• You need to know whether a graph has an odd cycle.
• A grid or board where neighbours must alternate, like black and white squares on a chessboard.

It looks like general graph colouring, which is hard for three or more colours. With exactly two colours there’s never a real choice to make, so a single BFS settles it.

The idea

Seat guests at two tables, where some pairs refuse to sit together. Put the first guest at table A. Everyone who dislikes them must go to table B. Everyone who dislikes those guests must go to table A, and so on. You never guess: each placement is forced by the one before. The plan fails only if two guests at the same table turn out to dislike each other.

That’s the whole algorithm. Colour a start node 0, give its neighbours colour 1, their neighbours colour 0, spreading outward with BFS. If you ever find an edge whose two ends already have the same colour, the graph isn’t bipartite. If no such edge turns up, the colours you wrote down are a valid split.

A same-colour edge always means an odd cycle. Walking around any cycle flips the colour at every step, so you only get back to the starting colour after an even number of steps. A cycle of 3 or 5 or 7 edges can’t be coloured, and a graph without odd cycles always can. That’s the classic theorem: bipartite ⇔ no odd cycle.

How it works

The graphic colours an 8-node graph with two separate pieces. Nodes sit in columns by their BFS distance from where their piece started, so the colours alternate column by column. Scroll through the steps and the graphic follows along.

Now the same code on a graph with a five-edge cycle, 0–1–3–4–2–0. Nodes 3 and 4 are both two steps from 0, so both get colour 0, and the edge between them is a conflict:

Why a clash really means “impossible”: the conflict edge joins node and a neighbour of the same colour, so both are an even distance or both an odd distance from the start. Their two BFS paths back to the node where they meet have lengths of the same parity, so the two paths plus the conflict edge form a cycle of odd length. No 2-colouring survives an odd cycle, so the answer isn’t just “this colouring failed”, it’s “every colouring fails”. And when there’s no clash, every edge was checked from at least one end, so every edge joins two different colours.

from collections import deque


def two_color(n, edges):
    """Colour nodes 0..n-1 with 0 and 1 so every edge joins different colours.
    Returns the colour list, or None if the graph isn't bipartite."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        if u != v:
            adj[v].append(u)

    color = [-1] * n                           # -1 = not coloured yet
    for s in range(n):                         # every component gets its own BFS
        if color[s] != -1:
            continue
        color[s] = 0
        queue = deque([s])
        while queue:
            node = queue.popleft()
            for nxt in adj[node]:
                if color[nxt] == -1:
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return None
    return color

#include <optional>
#include <queue>
#include <utility>
#include <vector>

// Colour nodes 0..n-1 with 0 and 1 so every edge joins different colours.
// Returns the colours, or std::nullopt if the graph isn't bipartite.
std::optional<std::vector<int>> twoColor(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        if (u != v) adj[v].push_back(u);
    }

    std::vector<int> color(n, -1);                     // -1 = not coloured yet
    for (int s = 0; s < n; s++) {                      // every component gets its own BFS
        if (color[s] != -1) continue;
        color[s] = 0;
        std::queue<int> queue;
        queue.push(s);
        while (!queue.empty()) {
            int node = queue.front();
            queue.pop();
            for (int nxt : adj[node]) {
                if (color[nxt] == -1) {
                    color[nxt] = 1 - color[node];
                    queue.push(nxt);
                } else if (color[nxt] == color[node]) {
                    return std::nullopt;
                }
            }
        }
    }
    return color;
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Bipartite {
    // Colour nodes 0..n-1 with 0 and 1 so every edge joins different colours.
    // Returns the colours, or null if the graph isn't bipartite.
    static int[] twoColor(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (e[0] != e[1]) adj.get(e[1]).add(e[0]);
        }

        int[] color = new int[n];
        Arrays.fill(color, -1);                        // -1 = not coloured yet
        for (int s = 0; s < n; s++) {                  // every component gets its own BFS
            if (color[s] != -1) continue;
            color[s] = 0;
            ArrayDeque<Integer> queue = new ArrayDeque<>();
            queue.add(s);
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int nxt : adj.get(node)) {
                    if (color[nxt] == -1) {
                        color[nxt] = 1 - color[node];
                        queue.add(nxt);
                    } else if (color[nxt] == color[node]) {
                        return null;
                    }
                }
            }
        }
        return color;
    }
}

The code tries neighbours in the order the edges were given and starts each component at its smallest node, so all three versions print the same colours.

Why it’s O(V + E)

It’s BFS with a colour instead of a distance. Each node is coloured once, enters the queue once and is dequeued once: O(V). Dequeuing a node scans its adjacency list, and the lists hold 2E entries in total: O(E). The outer loop over start nodes adds O(V), and each extra BFS only touches its own component.

Space is O(V + E) for the adjacency lists, plus O(V) for color and the queue.

Common mistakes

color[0] = 0; queue = deque([0])     # ✗ other components never checked
for s in range(n):                   # ✓ start a BFS at every uncoloured node
    if color[s] == -1: ...

adj[a].append(b)                          # ✗ half an edge
adj[a].append(b); adj[b].append(a)        # ✓ undirected

if find(u) == find(v): return False             # ✗ any cycle
if color[u] == color[v]: return False           # ✓ only same-colour edges

Variations

• Possible bipartition. People and “dislike” pairs: build the graph from the pairs (both directions) and run the same check. The two colours are the two groups. Labels often start at 1, so size the arrays n + 1.
• DFS version. Same rule, different order: colour the start 0, then recursively (or with a stack) give each uncoloured neighbour 1 - color[u] and report a clash when a coloured neighbour matches. Any traversal works, because each colour is forced by its neighbour.
• Union-find with parity. Store, for each node, whether its colour matches its parent’s. Merging u and v sets their relative colour to “different”; an edge between two nodes already in one set is a conflict when their parities are equal. Handy when edges arrive one at a time. A simpler form: union all of u’s neighbours together, and fail if u ends up in their set.
• Show the odd cycle. When a clash appears between u and v, walk BFS parents up from both until the paths meet. The two paths plus the edge u–v form an odd cycle, the proof that no split exists.
• Counting the splits. Each connected component can be flipped independently, so a bipartite graph with c components has 2^c valid colourings.