Bipartite Graph Detection
Last Updated: April 5, 2026
Imagine you are organizing a debate tournament. You have a list of participants, and some pairs of them refuse to be on the same team. Your job is to split everyone into exactly two teams so that no two people who refuse to cooperate end up together. Can you always find a valid split? And if you can, how do you figure it out efficiently?
This is the bipartite graph problem. Model each participant as a node, each conflict as an edge, and the question becomes: can you color every node with one of two colors so that no two adjacent nodes share the same color? If yes, the graph is bipartite. If not, there is no valid split, and the reason always comes down to the same thing: an odd-length cycle lurking in the graph.
What Is a Bipartite Graph?
A graph is bipartite if you can divide its vertices into two disjoint sets, say Set A and Set B, such that every edge connects a vertex in Set A to a vertex in Set B. No edge connects two vertices within the same set.
This is equivalent to saying the graph is 2-colorable: you can assign one of two colors to every vertex so that no two adjacent vertices share the same color.
There is a third, elegant way to think about it. A graph is bipartite if and only if it contains no odd-length cycle. A cycle of length 3 (triangle), 5, 7, or any odd number makes 2-coloring impossible. Even-length cycles are fine.
Why does an odd cycle break things? Picture a cycle with 3 nodes: A-B-C-A. Color A with 0. Then B must be 1 (it is adjacent to A). Then C must be 0 (it is adjacent to B). But C is also adjacent to A, and both are color 0. Contradiction. The same logic extends to any odd-length cycle.
The diagram below shows a bipartite graph on the left and a non-bipartite graph on the right. Notice the triangle in the non-bipartite graph, which makes a valid 2-coloring impossible.
In the bipartite graph, nodes A, B, C form one set (teal) and D, E, F form the other (orange). Every edge crosses between the two sets. In the non-bipartite graph, the triangle X-Y-Z makes 2-coloring impossible. No matter how you assign two colors, two adjacent nodes in that triangle will end up with the same color.
Real-World Applications
- Job assignment: Given a set of workers and a set of tasks, with edges indicating which workers can do which tasks, the resulting graph is bipartite. Algorithms like the Hungarian method and Hopcroft-Karp build on this bipartite structure to find optimal assignments.
- Course scheduling: Students and time slots form two sets. Conflicts (a student enrolled in two courses) create constraints. Checking if valid scheduling is possible often reduces to bipartite analysis.
- Social network analysis: In a network where users interact, determining if the community can be divided into two non-overlapping groups (say, buyers and sellers on a marketplace) is a bipartiteness check.
- Network flow: Many maximum flow and matching algorithms operate on bipartite graphs. The classic maximum bipartite matching problem is a direct application.
- Recommendation systems: User-item interaction graphs are naturally bipartite (users on one side, items on the other), and algorithms exploit this structure for collaborative filtering.
The Core Idea
The Problem
Given an undirected graph, determine whether it is bipartite. In other words, can you assign one of two labels (say 0 and 1) to every vertex so that no edge connects two vertices with the same label?
A brute-force approach would try all possible 2-colorings. With n vertices, there are 2^n possible assignments. For each assignment, you would check if every edge connects differently colored vertices. That is exponential and far too slow.
The Key Insight
You do not need to try all colorings. You can determine the correct coloring greedily using BFS or DFS. Here is why.
Pick any unvisited node and assign it color 0. Now, every neighbor of that node must be color 1 (there is no other valid choice). Every neighbor of those neighbors must be color 0. And so on. The coloring is forced at every step. There is no decision to make.
If, during this forced coloring, you ever find a neighbor that has already been colored and its color matches the current node's color, you have found a conflict. That conflict means the graph is not bipartite, and there is guaranteed to be an odd-length cycle passing through those two nodes.
Think of it like painting a fence where alternating posts must be different colors. You start with one color, alternate as you go, and if you ever circle back to a post that is already the wrong color, the fence has an odd number of posts in that loop, and alternating colors is impossible.
Visual Overview
The algorithm is a minor extension of standard BFS or DFS. Instead of just tracking "visited or not," you track the color assigned to each node. The rest of the traversal logic stays the same.
Approach 1: BFS
The BFS-based approach is the most common one you will see in interviews. Here is the step-by-step procedure.
- Initialize a color array of size V (number of vertices), filled with -1 to indicate "uncolored." This array serves double duty: it tracks both whether a node has been visited and what color it was assigned.
- Loop over all nodes. For each uncolored node, start a BFS from it. This outer loop handles disconnected components, which is critical. A graph can be bipartite overall even if it has multiple disconnected parts, as long as each part is independently bipartite.
- For the current BFS source, assign it color 0 and add it to the queue.
- While the queue is not empty, dequeue a node and examine each of its neighbors:
- If the neighbor is uncolored, assign it the opposite color (1 - current color) and enqueue it.
- If the neighbor is already colored and its color is the same as the current node, return false. The graph is not bipartite.
- If the neighbor is already colored and its color is different, everything is fine. Move on.
- If all nodes are colored without conflict, the graph is bipartite.
Approach 2: DFS
The DFS approach uses exactly the same coloring logic. The only difference is the traversal order: instead of expanding level by level, DFS goes deep along one path before backtracking.
The recursive version is particularly clean:
- Call
dfs(node, color)for each uncolored node. - Inside
dfs, assign the node its color. - For each neighbor, if uncolored, recursively call
dfs(neighbor, 1 - color). If the recursive call returns false, propagate the failure. - If the neighbor is already colored and has the same color as the current node, return false.
Both BFS and DFS have the same time and space complexity for this problem. BFS is often preferred in interviews because the iterative queue-based approach avoids potential stack overflow issues on very deep graphs. DFS is slightly more concise in its recursive form, which can be nice for quick whiteboard implementations.
Example Walkthrough
Let us trace through two examples to see the algorithm in action.
Example 1: A Bipartite Graph
Consider this graph with 6 nodes:
This forms a path-like structure: 0-1-2-3-4-5 with an extra edge 0-3.
Here is the BFS trace starting from node 0:
Every edge connects a teal node (color 0) to an orange node (color 1). The 2-coloring is valid.
Example 2: A Non-Bipartite Graph
Now consider a graph with a triangle:
Nodes 0, 1, 2 form a triangle (odd cycle of length 3).
The conflict happens at step 3 when we discover that node 2 (already colored 1) is a neighbor of node 1 (also colored 1). Both got the same color because they are both neighbors of node 0, but they are also neighbors of each other. This is the triangle 0-1-2, an odd cycle, and it makes 2-coloring impossible.
Implementation
The primary implementation uses BFS with a color array. The color array stores -1 for uncolored nodes, 0 for one color, and 1 for the other. The outer loop ensures all connected components are checked.
Code Explanation
The code follows the algorithm described earlier. A few things worth noting:
- The color array does triple duty. It tracks whether a node is visited (value != -1), which set/color it belongs to (0 or 1), and serves as the final partition if the graph turns out to be bipartite. This is cleaner than maintaining separate visited and color arrays.
- The `1 - color[node]` trick. This flips between 0 and 1. If the current node is color 0, the neighbor gets color 1, and vice versa. It is a concise way to express "opposite color."
- The outer for loop. This is essential for disconnected graphs. Without it, you would only check the component containing node 0 and miss conflicts in other components.
- The adjacency list representation. The input
graph[i]is a list of neighbors of node i. This is the format used by LeetCode 785 ("Is Graph Bipartite?"), so the code is directly interview-ready.
Common Mistakes:
- Forgetting the outer loop for disconnected components. If you only start BFS from node 0, disconnected non-bipartite components go undetected.
- Using a boolean visited array instead of a color array. You need three states (unvisited, color 0, color 1), not two (visited, unvisited).
- Checking the conflict condition incorrectly. The conflict is
color[neighbor] == color[node], notcolor[neighbor] != -1. A neighbor being colored is fine as long as the colors differ.
Complexity Analysis
Time Complexity
Overall: O(V + E)
The analysis is identical to standard BFS:
- Each vertex is enqueued and dequeued exactly once across the entire algorithm. This contributes O(V).
- For each vertex, we iterate over its adjacency list. Summing across all vertices, this is O(E) for an undirected graph (each edge is examined twice, once from each endpoint, but this is still O(E)).
- The outer loop iterates over all V vertices, but the inner BFS only processes vertices that have not been colored yet. So the total work across all BFS calls is O(V + E), not O(V * (V + E)).
Space Complexity
Overall: O(V)
- The color array takes O(V) space.
- The BFS queue can hold at most O(V) nodes in the worst case (for example, a star graph where all nodes are neighbors of the center).
- No additional data structures are needed.
Variations and Extensions
Variation 1: DFS-Based Detection
The DFS approach uses recursion instead of a queue. It is functionally equivalent but sometimes more concise to write on a whiteboard.
The logic mirrors BFS exactly. The only difference is traversal order: DFS colors one branch completely before moving to the next, while BFS colors level by level.
Variation 2: Union-Find Approach
Union-Find offers an alternative perspective. The idea is: for each node, all its neighbors must belong to the opposite group. So all neighbors of a node should be in the same group as each other.
For each node u, union all neighbors of u together. Then check if u and any of its neighbors ended up in the same group. If they did, the graph is not bipartite.
This approach has a time complexity of O(V + E * alpha(V)), where alpha is the inverse Ackermann function (effectively constant). It is slightly less intuitive than BFS coloring but can be useful if you are already using Union-Find for other parts of the problem.
Variation 3: k-Colorability
Bipartite checking is the k=2 case of graph coloring. A natural question is: what about 3-colorable, 4-colorable, etc.? Unfortunately, determining if a graph is k-colorable for k >= 3 is NP-complete. There is no known polynomial-time algorithm. This makes the k=2 case special, and it is one of the few graph coloring problems that can be solved efficiently.
Comparison Table
| Approach | Time Complexity | Space Complexity | Best For |
|---|---|---|---|
| BFS Coloring | O(V + E) | O(V) | Interviews, iterative preference |
| DFS Coloring | O(V + E) | O(V) | Quick whiteboard, recursive preference |
| Union-Find | O(V + E * alpha(V)) | O(V) | When Union-Find is already in use |
Comparison with Related Algorithms
| Algorithm | Purpose | Time | Space | Key Difference |
|---|---|---|---|---|
| BFS 2-Coloring | Bipartite detection | O(V + E) | O(V) | Colors nodes with 2 colors during traversal |
| DFS 2-Coloring | Bipartite detection | O(V + E) | O(V) | Same result, different traversal order |
| Union-Find | Bipartite detection | O(V + E * alpha(V)) | O(V) | Groups neighbors, checks for conflicts |
| DFS Cycle Detection | Find any cycle | O(V + E) | O(V) | Detects cycles but does not check parity |
| Graph Coloring (k >= 3) | k-colorability | NP-complete | - | No efficient algorithm known for k >= 3 |
When to Choose BFS 2-Coloring
- You need a straightforward, interview-friendly solution.
- The graph might be very deep (avoiding recursion stack overflow).
- You want to track the level or distance of each node as a bonus.
When NOT to Use BFS 2-Coloring
- The problem asks for k-coloring with k >= 3 (NP-complete, different problem entirely).
- You are already maintaining a Union-Find structure and want to avoid adding BFS on top.
- The graph is represented as an edge list and converting to adjacency list is expensive (though this is rare in practice).
Common Patterns and Applications
Pattern 1: Partition Into Two Groups
Problem type: "Can we divide n elements into two groups such that no two elements in the same group have a conflict?"
How bipartite detection helps: Model elements as nodes, conflicts as edges. Run bipartite check. If the graph is bipartite, the two color classes give you the partition. If not, no valid partition exists.
Example: LeetCode 886 "Possible Bipartition" asks exactly this. Given n people and a list of pairs who dislike each other, can you split them into two groups so no one is in the same group as someone they dislike?
Pattern 2: Conflict Resolution
Problem type: "Assign one of two labels to each node respecting edge constraints."
How bipartite detection helps: This is literally 2-coloring. Any problem that asks you to assign binary labels (true/false, 0/1, team A/team B) to nodes with pairwise constraints is a bipartite check in disguise.
Pattern 3: Foundation for Matching
Problem type: Maximum matching, minimum vertex cover, or assignment problems on bipartite graphs.
How bipartite detection helps: Many matching algorithms (Hopcroft-Karp, Hungarian method) require the input graph to be bipartite. The first step is often verifying bipartiteness. Once confirmed, you can apply specialized bipartite matching algorithms that are more efficient than general matching algorithms.