Bipartite graph explained
How the bipartite graph interview pattern works, why odd cycles break two coloring, and how to spot disguised variants in coding problems.
What makes a graph bipartite and why the property matters
Why odd-length cycles are the single disqualifying condition
How the BFS two-coloring algorithm works step by step
When bipartite detection appears in interviews and how to spot it
What makes a graph bipartite, and why does the bipartite graph interview pattern keep showing up? Both questions have the same answer. A graph is bipartite if and only if it contains no odd-length cycle. Two-coloring detects this in O(V + E) time, and the algorithm is BFS with a single twist: you assign colors as you go and check for conflicts.
What bipartite actually means
A graph is bipartite if you can split its nodes into two groups so that every edge connects a node in one group to a node in the other. No edge ever connects two nodes within the same group.
The practical version is simpler: can you separate everything into two sides with no conflicts?
Scheduling works as an example here. You've got tasks and machines, and certain tasks conflict with certain machines. If you can assign every task to a machine with no conflict, the underlying constraint graph is bipartite. Matching problems and graph coloring with exactly two colors have the same shape.
In interviews, you won't always see the word "bipartite" in the problem statement. You'll see "can you divide into two groups such that [condition]" or "is it possible to assign two labels so that no adjacent pair shares a label." Spotting that these are bipartite detection problems is half the battle.
Why odd cycles break bipartiteness
This is the invariant that makes the entire algorithm work, and most explanations gloss over it. If you understand why odd cycles are the problem, the algorithm stops being something you memorise and becomes something you can derive on a whiteboard.
Take a triangle with nodes A, B, C, all connected. Color A red, so B must be blue (adjacent to A), and C must be red (adjacent to B). But C is also adjacent to A, which is already red. Conflict. You can't two-color a triangle.
Now try a square: A, B, C, D. Color A red, B blue, C red, D blue. D is adjacent to A, and they're different colors. Works fine.
The pattern holds for every cycle length. Even-length cycles alternate cleanly. Odd-length cycles always force a conflict on the closing edge.
“A graph is bipartite if and only if it contains no odd-length cycle. Every other property follows from this single invariant.”
Matching algorithms in scheduling and network flow rely on bipartite structure, and the odd-cycle theorem is the mathematical foundation they build on. That's a separate topic, but the invariant you're using in a 20-minute interview problem underpins an entire family of optimisation algorithms. Worth keeping in the back of your mind if the interviewer asks "why does this matter outside of interview problems?"
The two coloring algorithm step by step
The detection algorithm is BFS with one addition. You assign colors as you traverse and check for conflicts.
- 1Pick any uncolored node. Assign it color 0.
- 2Add it to a BFS queue.
- 3For each node you dequeue, look at its neighbors. If a neighbor hasn't been colored, assign it the opposite color and enqueue it. If a neighbor already has the same color as the current node, the graph isn't bipartite. Return false.
- 4If the queue empties without conflicts, repeat from step 1 for any remaining uncolored nodes (this handles disconnected components).
- 5If all components pass, the graph is bipartite.
Let's trace it on a concrete graph with six nodes and edges 0-1, 0-3, 1-2, 2-3, 3-4, 4-5.
Python
Start at node 0 with color 0. Neighbors 1 and 3 get color 1. Process node 1, neighbor 2 gets color 0. Process node 3, neighbor 2 is already color 0 while node 3 is color 1, different colors, no conflict. Neighbor 4 gets color 0. Process node 2, neighbor 3 is color 1 against node 2's color 0, clean. Process node 4, neighbor 5 gets color 1. Queue empties. The graph is bipartite.
Now add edge 1-3, creating a triangle with nodes 0, 1, 3. Process node 0 (color 0), color neighbors 1 and 3 as color 1. Process node 1, neighbor 3 is already color 1, same as node 1. Conflict. Return false. The triangle gets caught immediately.
1 - color[node] trick flips between 0 and 1 without branching. It's the standard way to alternate colors in two-coloring implementations.Time complexity is O(V + E), same as standard BFS. You visit every node once and check every edge once. Space is O(V) for the color array and queue.
When bipartite graph detection shows up in interviews
You won't always see "is this graph bipartite?" as the problem title. The pattern hides behind different framings.
- "Can you divide into two groups?" You're given people and pairs who dislike each other. Can you split them into two groups where no one in the same group dislikes anyone else? That's bipartite detection on the dislike graph.
- "Is this graph two-colorable?" Direct synonym. The map coloring variant asks whether regions can be painted with exactly two colors so no adjacent regions share a color.
- "Can you assign labels with no constraint violations?" Any binary assignment problem on a graph reduces to bipartite checking if the constraints are pairwise.
The triggers are a graph (explicit or implicit), a binary property assigned to each node, and the constraint that adjacent nodes can't share the same assignment.
On Codeintuition, the two-coloring identification lesson trains you to spot these triggers before you see a problem's solution. The pattern covers four problems: bipartite detection itself, dislike pairs, colour repair, and group colourability. Four different surfaces, one underlying check.
Common bipartite graph interview mistakes
- Forgetting disconnected components. It is the most common bug. If the graph has multiple connected components, you need to run BFS from every unvisited node. A single BFS from node 0 only checks one component. The outer loop in the code above handles this, but it's easy to forget when writing from scratch under time pressure.
- Assuming directed graphs behave differently: It trips up candidates who overthink the problem. For bipartite detection, treat every directed edge as undirected. The direction doesn't affect whether the graph can be two-colored. If your interviewer specifies a directed graph, clarify whether they want bipartite detection on the underlying undirected structure.
- Starting node choice doesn't matter: Every node in a connected component gets visited regardless of where you start, so don't spend interview time deliberating about it.
- Confusing bipartite with acyclic is a conceptual error: A graph can have cycles and still be bipartite. It just can't have odd-length cycles. A square (4-cycle) is bipartite. A hexagon (6-cycle) is bipartite. Only odd cycles break the property. This distinction catches a surprising number of candidates off guard, especially when the interviewer asks follow-up questions about why a particular graph with cycles still passes the two-coloring check.
Most of these mistakes share a root cause: candidates memorise the algorithm without internalising the odd-cycle invariant. They don't know which edge cases actually matter.
Quick checklist before submitting: outer loop handles disconnected components, don't treat directed edges specially unless told to, cycles alone don't mean non-bipartite (only odd cycles do), and color[neighbor] == color[node] is your conflict check, not color[neighbor] != -1.
Where two coloring fits
Bipartite detection is one of five graph patterns covered in the guide. It sits alongside DFS path enumeration, connected components, BFS shortest-path applications, and Dijkstra's weighted shortest path.
The understanding lesson for two-coloring walks through the odd-cycle invariant with frame-by-frame illustrations before you see any code. The identification lesson then teaches you to spot the pattern in problems that don't say "bipartite." Understand the invariant, learn the triggers, then apply to problems with increasing difficulty. Codeintuition's Graph course covers 40 lessons, 37 problems, and 5 patterns with 289 illustrations, and the two-coloring section alone has four problems that look completely different on the surface but all reduce to the same BFS coloring check.
You don't just drill the pattern on identical problems. You train it across varied contexts so the identification skill transfers to new problems. The free courses on arrays and linked lists use the same three-phase teaching model on foundational patterns like two pointers and sliding window. If the invariant-first approach here clicked, try the identification lessons for those patterns and see whether reading the triggers before attempting problems changes how you approach unfamiliar ones.
The hard part was never implementing BFS two-coloring. It's recognising that a problem requires it when the word "bipartite" never appears in the description.
Do you want to master data structures?
Try our data structures learning path made of highly visual and interactive courses. Get hands on experience by solving real problems in a structured manner. All resources you would ever need in one place for FREE