Bipartite check

O(V + E)

A graph is bipartite when you can split its vertices into two sets so that every edge connects a vertex in one set to a vertex in the other — never within a set. Equivalently, it has no odd-length cycle. To test it, BFS-colour the graph: give the start colour A, every neighbour the opposite colour, and so on. If you ever reach an edge whose endpoints already share a colour, that's a same-side edge and the graph isn't bipartite. The sweep is O(V + E). Bipartite structure underlies matching problems, scheduling, and two-sided markets.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. Colour the start vertex A.
  2. Give every uncoloured neighbour the opposite colour and enqueue it.
  3. If an edge joins two vertices of the same colour, stop — not bipartite.
  4. If every vertex gets coloured without conflict, the graph is bipartite.

Pseudocode

1isBipartite(graph):                  # O(V + E)2  for each uncoloured vertex s:3    colour[s] ← 0; queue ← [s]4    while queue not empty:5      u ← queue.dequeue()6      for v in neighbours(u):7        if v uncoloured:8          colour[v] ← 1 − colour[u]   # opposite side9          queue.enqueue(v)10        else if colour[v] = colour[u]:11          return false                # same-side edge → odd cycle12  return true