What Is a Bipartite Graph? Odd Cycles, Two Colors, One Test
- Bipartite graph: vertices split into two disjoint sets where every edge crosses between them; equivalent to 2-coloring with no same-color adjacent vertices.
- Detection algorithm: BFS or DFS coloring runs in O(V + E); assign one color to the start node, flip for each neighbor, return false the moment two adjacent nodes share a color.
- Odd cycle theorem: a graph is bipartite if and only if it contains no odd-length cycle; the 2-coloring check finds odd cycles implicitly without searching for them.
- Trees are always bipartite: no cycles means no odd cycles; even-depth vertices form one set, odd-depth the other, so the check can be skipped entirely.
- Interview reframe: "divide into two groups with pairwise constraints" maps directly to bipartite checking (LeetCode 785, 886); one-to-one assignment maps to bipartite matching.
- Bipartite matching: the Hopcroft-Karp algorithm solves maximum matching in O(E√V); König's Theorem links minimum vertex cover to maximum matching in bipartite graphs only.
- 2-coloring is the tractable case: general k-coloring is NP-hard for k ≥ 3; k = 2 reduces to O(V + E) bipartite detection.
You have 50 people, two conference rooms, and a spreadsheet of who hates whom. Your job: split everyone so no enemies share a room. Sound like an HR problem? It's a graph problem. And it has a clean O(V + E) solution.
Bipartite graphs show up in scheduling, recommendation systems, and matching problems. They also hide inside a class of interview questions that look nothing like graphs until you see the structure. Once you see it, you'll recognize it before you finish reading the problem.
Two Sets, Every Edge Crosses
A graph is bipartite if its vertices can be divided into two disjoint sets, U and V, such that every edge connects a vertex in U to a vertex in V. No edge connects two vertices in the same set.
The textbook example: an actor-movie graph. One set is actors, the other is movies. An edge means an actor appeared in that movie. Actors don't connect to actors. Movies don't connect to movies. Every edge crosses.
Actors Movies
A1 --------- M1
A1 --------- M2
A2 --------- M2
A2 --------- M3
A3 --------- M1
The two-set definition is correct, but it's not how you'd detect bipartiteness in code. There's a cleaner lens: a graph is bipartite if and only if you can color every vertex with one of two colors such that no two adjacent vertices share a color. Assign U "red" and V "blue," and every edge runs red-to-blue. Both definitions are equivalent.
Two Colors Are All You Need
Run BFS from any unvisited vertex. Color it red. Color all its neighbors blue. Color their unvisited neighbors red. Continue until you run out of vertices or hit a conflict.
Two things can happen. You finish coloring the whole graph without a conflict. Bipartite. Or you find a neighbor that already has the same color as the current vertex. Not bipartite. That conflict means two adjacent vertices landed in the same set, which breaks the partition.
from collections import deque def is_bipartite(graph: list[list[int]]) -> bool: n = len(graph) color = [-1] * n # -1 = unvisited for start in range(n): if color[start] != -1: continue color[start] = 0 queue = deque([start]) while queue: node = queue.popleft() for neighbor in graph[node]: if color[neighbor] == -1: color[neighbor] = 1 - color[node] queue.append(neighbor) elif color[neighbor] == color[node]: return False return True
The outer loop is not optional. A graph can have multiple connected components, and each needs its own BFS pass. A graph is bipartite only if every component passes the check.
Time: O(V + E). Every vertex and edge visited once. Space: O(V) for the color array and queue.
You can use DFS instead of BFS. Same logic: propagate a color, flip it at each step, return false on conflict. BFS is usually easier to reason about here.
Odd Cycles Are the Villain
A graph is bipartite if and only if it contains no odd-length cycle.
Trace any cycle using the 2-coloring approach: each step flips the color. After an even number of steps, you return to the starting color. No conflict. After an odd number of steps, you return with the wrong color. Conflict.
Take a triangle (three vertices, three edges). Color the first vertex red, the second blue, the third must be red because it neighbors blue. But the third vertex connects back to the first, which is also red. Two adjacent red vertices. Not bipartite. Three people who all hate each other cannot be split into two groups where no enemies share one. Someone is always stuck.
Any graph with a triangle fails. Any graph with a 5-cycle fails. The BFS algorithm finds these odd cycles implicitly without ever searching for them directly. It just tries to color and reports the contradiction when it finds one.
An odd cycle in a graph works exactly like this. The conflict reports itself.
Trees Are Free Points
Trees have no cycles at all, so they have no odd cycles. Every tree is bipartite. If a problem tells you the graph is a tree, skip the check entirely.
The bipartition falls out naturally from BFS level order: vertices at even depth form one set, vertices at odd depth form the other. Two vertices at the same depth never share an edge in a tree because that edge would create a cycle, which would contradict the tree property.
Three Bipartite Problems in Disguise
Is Graph Bipartite? (LeetCode 785)
The direct application. The BFS template above is the solution. Two traps: disconnected graphs (the outer loop handles them) and self-loops (a self-loop is a cycle of length 1, which is odd, so it disqualifies the graph immediately).
Possible Bipartition (LeetCode 886)
N people and a list of pairs who cannot be in the same group. Can you split everyone into two groups so no conflicting pair ends up together?
Build a graph where an edge means "these two must be in opposite groups." Check if that graph is bipartite. If it is, the two color classes are your groups.
The reframe is the entire problem. Once you see "divide into two groups with pairwise constraints," you're looking at bipartite checking. The code is three minutes once you see it. The recognition is what the interviewer is actually testing.
The Maximum Matching Problem
Bipartite checking tells you whether a partition exists. Bipartite matching finds the best assignment within that partition.
Given a bipartite graph, find the maximum number of edges such that no vertex appears in more than one selected edge. This models one-to-one assignment: workers to shifts, candidates to roles, students to dorm rooms. The Hopcroft-Karp algorithm solves it in O(E√V).
Real-world bipartite matching in the wild. The algorithm works whether you're assigning workers to shifts or friends to each other.
One result worth knowing: König's Theorem says that in a bipartite graph, the minimum vertex cover equals the maximum matching. This does not generalize to non-bipartite graphs. Senior-level interviewers sometimes ask about it directly.
Graph Coloring With k = 2
General graph coloring (assign k colors so no adjacent vertices share a color) is NP-hard for k ≥ 3. The k = 2 case is bipartite checking, which runs in O(V + E). If a problem asks whether a graph can be 2-colored, you already know the algorithm.
The Numbers
| Operation | Time | Space |
|---|---|---|
| Bipartite detection (BFS or DFS) | O(V + E) | O(V) |
| Maximum bipartite matching (Hopcroft-Karp) | O(E√V) | O(V + E) |
The Short Version
- A bipartite graph divides vertices into two sets where every edge crosses between them.
- Equivalent: 2-colorable, no two adjacent vertices share a color.
- No odd-length cycle means bipartite. Any odd cycle disqualifies it.
- Trees are always bipartite.
- Detection: O(V + E) using BFS or DFS. Loop over all vertices to handle disconnected components.
- Interview signal: "divide into two groups with pairwise constraints" maps to bipartite checking. One-to-one assignment maps to bipartite matching.
- The reframe is harder than the algorithm. Train yourself to see the two-coloring structure first.
Bipartite detection is clean graph theory, but interviews test whether you can explain your reasoning under pressure, not just produce correct code. SpaceComplexity runs voice-based mock interviews on graph problems including bipartite checking, cycle detection, and the matching reframe, with rubric-based feedback after each session. Worth a run before your next loop.