On this page
Description
A graph is bipartite when its nodes can be split into two groups so that every edge goes between the groups and never inside one. Examples are workers and tasks, or two teams where certain pairs must be on opposite sides. Trying all 2^n splits is hopeless, but one traversal settles it: color the first node, and every other color in its component is forced. This skill covers the check, choosing the sides, and why an odd cycle is exactly what makes a split impossible.
We'll go from simple to more technical:
- The pattern: BFS 2-coloring with a contradiction check.
- A second flavor: choosing the sides by flipping components.
- Where two-sided splits show up (matching, scheduling, seating).
- What breaks it: one component only, no contradiction check, and fixed colorings.
The approach
Java
boolean isBipartite(int n, List<List<Integer>> adj) {
int[] color = new int[n];
Arrays.fill(color, -1); // -1 = not colored yet
for (int start = 0; start < n; start++) { // every component separately
if (color[start] != -1) continue;
Deque<Integer> queue = new ArrayDeque<>();
color[start] = 0;
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int next : adj.get(node)) {
if (color[next] == -1) {
color[next] = 1 - color[node]; // forced: the opposite side
queue.add(next);
} else if (color[next] == color[node]) {
return false; // an edge inside one side - impossible
}
}
}
}
return true;
}
Python
from collections import deque
def is_bipartite(n: int, adj: list[list[int]]) -> bool:
color = [-1] * n # -1 = not colored yet
for start in range(n): # every component separately
if color[start] != -1:
continue
color[start] = 0
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in adj[node]:
if color[nxt] == -1:
color[nxt] = 1 - color[node] # forced: the opposite side
queue.append(nxt)
elif color[nxt] == color[node]:
return False # an edge inside one side - impossible
return True
Nothing is guessed except each component's first node. After that every color is forced: a neighbor must be on the other side. So if the traversal ever finds an edge whose two ends got the same color, no split exists at all - not just for this coloring. That contradiction always comes from an odd cycle: going around a cycle alternates colors, so an odd-length cycle arrives back at its start with the wrong color. A triangle is the smallest example; any tree, and any even cycle, is bipartite.
A second flavor: choosing the sides
Since only the first node of each component is a free choice, each component's coloring can be flipped independently. That matters when the question asks about the sides themselves - for example, the largest possible size of one side:
Java
int[] count = new int[2]; // per component, counted during its BFS
...
total += Math.max(count[0], count[1]); // put the bigger color class on side A
Python
count = [0, 0] # per component, counted during its BFS
...
total += max(count) # put the bigger color class on side A
On a star with center 0 and leaves 1, 2, 3, coloring the center 0 gives side sizes 1 and 3 - adding up color 0 across components would report 1 instead of 3. Each component contributes its larger color class.
Where you'll see it
Matching problems (jobs to machines, students to schools, ads to slots) are modeled as bipartite graphs, and the matching algorithms assume the two sides are known - this check finds them. Two-coloring also underlies "split into two conflict-free groups" tasks, like scheduling two shifts where certain pairs can't share one.
Which tool for which job?
| You need | Use |
|---|---|
| Is the graph bipartite? | BFS or DFS 2-coloring with an outer loop over components |
| Proof that it isn't | the odd cycle found at the contradiction |
| The largest possible side | per component, add the larger color class |
| Edges arriving one at a time | union-find with parity |
| A grid or a tree | always bipartite: color by (r + c) % 2 or by depth |
| Three or more groups | no fast general method: 3-coloring is NP-complete |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Checking one component | a triangle elsewhere is missed | an outer loop over every uncolored node |
| Coloring without checking | always reports "bipartite" | compare colors on every already-colored neighbor |
| Treating each component's coloring as fixed | side sizes come out wrong (1 instead of 3 on a star) | each component can be flipped |
| Recursive DFS coloring on a long path | stack overflow | BFS |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Is a 4-cycle bipartite? A triangle?
Show answer
The 4-cycle is: colors alternate 0, 1, 0, 1 around it and the last edge connects 1 back to 0. The triangle isn't: 0, 1, then the third node must differ from both - impossible. Odd cycles are exactly what makes a graph non-bipartite.
2. The graph has edges 0-1, 2-3, 3-4 and 4-2. A check that starts only from node 0 reports "bipartite". Why is that wrong?
Show answer
Starting from 0 only colors the component {0, 1}. The triangle 2-3-4 is a separate component that's never examined. Every component has to be checked - loop over all nodes and start a new coloring from each uncolored one.
3. For a bipartite graph, how do you get the largest possible size of one side?
Show answer
Color each component, count its two color classes, and add the larger of the two for every component. Each component's coloring can be flipped on its own, so each can put its bigger class on the same side.
Key takeaways
- Bipartite means the nodes split into two sides with every edge crossing - equivalently, 2-colorable, equivalently, no odd cycle.
- Color each component's first node, force every neighbor to the opposite color, and fail on any same-colored edge.
- The check must run on every component.
- Each component's coloring can be flipped independently - relevant whenever the question asks about the sides.
- O(V + E): the coloring is a by-product of one traversal.