A graph is bipartite if its vertices can be split into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. Equivalently, the graph can be colored with two colors so that no edge has both endpoints in the same color.

This chapter covers what makes a graph bipartite, why bipartiteness fails exactly when an odd-length cycle exists, and three algorithms to detect it: BFS coloring, DFS coloring, and Union-Find.

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 way to characterize 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? Consider 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, which contradicts the coloring rule. 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. The triangle in the non-bipartite graph 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

The Problem

Given an undirected graph, determine whether it is bipartite: 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.

Pick any unvisited node and assign it color 0. 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, with no decision to make.

If, during this forced coloring, you 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.

Visual Overview

The algorithm is a minor extension of standard BFS or DFS. Instead of tracking only "visited or not," you track the color assigned to each node. The rest of the traversal logic stays the same.

The BFS-based approach is a common one in interviews. Use a color array of size V filled with -1 (uncolored) that doubles as the visited marker. For each uncolored node, BFS outwards: color the source 0, assign every newly discovered neighbor the opposite color of the current node, and return false the moment a neighbor that is already colored matches the current node's color.

The outer loop over all nodes handles disconnected components, which is critical since a graph can be bipartite overall even if it has multiple disconnected parts.

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.

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:

Common Mistakes:

Time Complexity

Overall: O(V + E)

The analysis is identical to standard BFS:

Space Complexity

Overall: O(V)

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

When to Choose BFS 2-Coloring

When NOT to Use BFS 2-Coloring

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.