Graph AlgosAlgorithmaka 2-colouring, two-colourable graph, odd cycle detection

Bipartite Check

Colour vertices with two colours so every edge joins different colours; succeeds iff the graph has no odd cycle.

▶ VisualizePattern: Breadth-First SearchPractice (1)
Progress

Overview

A graph is bipartite if its vertices can be split into two sets A and B such that every edge has one endpoint in each. Equivalently, it can be 2-coloured: adjacent vertices always get different colours. Equivalently again, it contains no cycle of odd length.

The test is a traversal that assigns colours greedily: start a vertex with colour 0, give every neighbour colour 1, their neighbours colour 0, and so on. If an edge is ever found between two vertices of the same colour, the graph is not bipartite; if the traversal finishes every component without conflict, it is. Breadth-First Search (BFS) or Depth-First Search (DFS) both work; BFS is the usual choice because layers alternate colours naturally.

Bipartiteness is a prerequisite for matching algorithms (Hopcroft–Karp), for "split people into two groups with no dislikes inside a group" problems, and for grid problems: any grid graph is bipartite by chessboard parity.

undirectedBFSDFS2-colouringodd cycleO(V + E)

Intuition

A mental model before the formal terms.

You are seating guests at two long tables and each edge says "these two must not sit together". Seat someone at table A; all their enemies go to B; enemies of those go to A. Walk outward like ripples. Trouble arises only if a ripple loops back and forces someone to sit at both tables — which happens exactly when a loop of enemies has odd length (going around an odd cycle flips the table an odd number of times and lands you on the wrong side).

Example: triangle 0—1—2—0. Colour 0 red, 1 blue, 2 red — but 2—0 joins two reds. Odd cycle, not bipartite. Square 0—1—2—3—0: red, blue, red, blue; 3—0 is blue–red. Bipartite.

How it works

  1. Initialise color[v] = -1 (uncoloured) for all vertices.
  2. For each uncoloured vertex s (one per component): set color[s] = 0 and push s into a queue.
  3. Pop u; for each neighbour v: if color[v] == -1, set color[v] = 1 - color[u] and enqueue; else if color[v] == color[u], return not bipartite.
  4. If every component is processed without conflict, return bipartite; color gives the partition.
  5. DFS version: dfs(u, c) colours u with c and recurses with 1 - c; identical conflict rule.

Why it works

If the traversal completes, color is a valid 2-colouring by construction: every edge was examined from at least one endpoint and passed the "different colour" check.

If a conflict occurs on edge u — v with color[u] == color[v], then in the BFS tree u and v are at depths of the same parity (colour = depth mod 2). The tree path between them has even length, and adding the edge u — v gives a closed walk of odd length, which contains an odd cycle. An odd cycle can never be 2-coloured (alternating around it returns to the start with the opposite colour), so the graph is indeed not bipartite.

Every vertex is enqueued once and every edge examined twice: O(V + E).

Recognition

How to tell a problem wants this.

  • "Split into two groups such that no pair in the same group are …", "possible bipartition", "two teams".
  • "Is the graph bipartite", or a matching / assignment problem between two kinds of objects.
  • Any question about odd cycles.
  • Grid problems where cells alternate like a chessboard — implicitly bipartite, which often unlocks a parity argument.
“minimum steps” → Breadth-First Search“connected groups” → Depth-First Search“connected groups” → Union-Find

Interactive visualization

Play, step, change the input. ← → and space work too.

ABCDEFGHIJKL
Queue
empty
1/26A graph is bipartite iff it can be 2-colored so that every edge joins different colors. BFS forces the coloring: each neighbor must take the opposite color, so any conflict proves an odd cycle.
Color 0Color 1Current nodeEdge used to color a neighborConflict: both ends same color
PseudocodeLearn Bipartite Check →
1color = {}
2for s in nodes:
3  if s in color: continue
4  color[s] = 0; queue = [s]
5  while queue not empty:
6    u = queue.popleft()
7    for v in neighbors(u):
8      if v not in color: color[v] = 1 - color[u]; queue.append(v)
9      elif color[v] == color[u]: return NOT bipartite
10return bipartite
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1color[*] = -1
2for s in 0..n-1:
3  if color[s] != -1: continue
4  color[s] = 0; queue = [s]
5  while queue not empty:
6    u = queue.popleft()
7    for v in adj[u]:
8      if color[v] == -1: color[v] = 1 - color[u]; queue.append(v)
9      else if color[v] == color[u]: return false
10return true

Implementations

1from collections import deque
2from typing import Optional
3 
4 
5def two_colour(adj: list[list[int]]) -> Optional[list[int]]:
6    """A graph is bipartite iff its vertices can be 2-coloured with no edge
7    joining two same-coloured vertices — equivalently, iff it has no
8    odd-length cycle. Returns the colouring, or None if not bipartite."""
9    n = len(adj)
10 
111 · colour[v] is -1 (unassigned), 0, or 1
12    colour = [-1] * n
13 
142 · Every component is coloured independently
15    for s in range(n):
16        if colour[s] != -1:
17            continue
18        colour[s] = 0
19        q = deque([s])
20 
213 · BFS assigns the opposite colour one layer out
22        while q:
23            u = q.popleft()
24            for v in adj[u]:
25                if colour[v] == -1:
26                    colour[v] = colour[u] ^ 1  # XOR flips 0 <-> 1
27                    q.append(v)
28                elif colour[v] == colour[u]:
294 · Same colour on both ends: an odd cycle, not bipartite
30                    return None
31    return colour
32 
33 
34def is_bipartite(adj: list[list[int]]) -> bool:
35    return two_colour(adj) is not None
36 
37 
385 · The two sides fall straight out of the colouring
39def sides(colour: list[int]) -> tuple[list[int], list[int]]:
40    left = [v for v, c in enumerate(colour) if c == 0]
41    right = [v for v, c in enumerate(colour) if c == 1]
42    return left, right
Walkthrough
  1. colour[u] ^ 1 works on Python ints exactly as elsewhere; ^ is bitwise XOR, not exponentiation (that is **).
  2. collections.deque gives O(1) popleft, so the BFS is linear with no head-cursor workaround.
  3. Optional[list[int]] (equivalently list[int] | None) makes the failure case explicit in the signature.
  4. is_bipartite uses is not None rather than a truthiness test, which matters because an empty list is falsy but a valid colouring.
  5. sides uses two comprehensions over enumerate, which is clearer than a single loop with a conditional append.
Complexity (this implementation)
time O(V + E) · space O(V)
Language notes
  • ^ is XOR in Python; ** is exponentiation. Coming from other languages, colour[u] ^ 1 is occasionally mistyped as colour[u] ** 1, which is a no-op.
  • networkx.is_bipartite and networkx.bipartite.sets cover both functions directly.
  • Optional[X] and X | None are the same type; the latter needs Python 3.10+ at runtime or from __future__ import annotations.
  • if two_colour(adj): would be wrong for an empty graph, since [] is falsy — hence the explicit is not None.
Common mistakes in this language
  • Testing the result with if two_colour(adj):, which treats a valid empty colouring as a failure.
  • Using a list with pop(0) instead of a deque for the BFS queue.
  • Colouring only the first component and reporting the whole graph as bipartite.
Language differences that matter here
  • Signalling "not bipartite": TypeScript and Python express it in the type (| null, Optional), while C++ and JavaScript return a sentinel — and in C++ the empty vector genuinely collides with the empty-graph case, forcing an extra guard.
  • Truthiness is a live hazard only in Python and JavaScript: an empty valid colouring is falsy, so the check must be is not None / !== null rather than a bare truth test.
  • The BFS queue splits the same way it always does — collections.deque and std::queue are O(1) at the front, JS/TS need the head-cursor array.
  • ^ means XOR in all four languages, but Python is the one where the neighbouring ** operator makes a typo silently harmless-looking rather than a syntax error.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Union-find with parity ("enemy of my enemy") also works in O(E α(V)) and supports online edge insertion.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Two-group partition problems with "cannot be together" constraints.
  • Before running bipartite matching or flow-based assignment.
  • Detecting odd cycles, or proving a parity argument on a grid or lattice graph.
Avoid it when
  • Three or more groups — k-colouring for k ≥ 3 is NP-hard in general; the greedy approach does not extend.
  • Directed graphs where direction matters — bipartiteness is an undirected notion; ignore directions first if that is what the problem means.
  • Edges arriving online with queries — prefer union-find with parity to avoid re-running BFS.

Alternatives

Breadth-First Search (BFS)Depth-First Search (DFS)Union-Find (Disjoint Set Union)Cycle Detection

Common mistakes

  • Only starting from vertex 0 and ignoring other components — a disconnected component can hold the odd cycle.
  • Checking colours only when a vertex is *dequeued* rather than at every edge, so same-colour edges between already-coloured vertices go unnoticed.
  • Treating "not bipartite" as "has a cycle" — even cycles are fine; only odd cycles break bipartiteness.
  • Forgetting self-loops: a self-loop u — u makes the graph non-bipartite immediately.

Interview patterns

  • Is Graph Bipartite: direct BFS colouring.
  • Possible Bipartition: build the "dislike" graph, colour it.
  • Union-find with parity: find returns (root, parity); conflict when two vertices with the same parity relative to the same root are joined.
Interview questions on this
Mock interviews

Example problems

Is Graph Bipartite?medium