AlgoMaster Logo

Is Graph Bipartite?

Last Updated: March 28, 2026

medium
5 min read

Understanding the Problem

We're given an undirected graph and need to decide whether we can split all its nodes into two groups such that no edge connects two nodes within the same group. This is the classic graph bipartiteness problem, and it comes up surprisingly often in disguise (scheduling, matching, conflict resolution).

Here's the key insight: a graph is bipartite if and only if it contains no odd-length cycles. Think about it. If you try to 2-color a cycle of length 3 (a triangle), you'll always end up with two adjacent nodes sharing the same color. But a cycle of length 4 can be perfectly 2-colored by alternating colors.

So the problem reduces to: can we assign one of two colors to every node such that no two adjacent nodes share the same color? If we can, the graph is bipartite. If we ever find a conflict (a node's neighbor already has the same color), it's not.

One detail that's easy to miss: the graph may not be connected. We need to check every connected component independently. A graph is bipartite only if all of its components are bipartite.

Key Constraints:

  • 1 <= n <= 100 -> Very small graph. Even O(n^2) or O(n^3) solutions would be fast. But the standard BFS/DFS approach is already O(V + E), which is optimal.
  • 0 <= graph[u].length < n -> Each node can have up to n-1 neighbors, so the graph can be dense. In the worst case, E = O(n^2) = O(10,000). Still tiny.
  • The graph may not be connected -> We must handle multiple components.

Approach 1: BFS (Graph Coloring)

Intuition

The most natural way to check bipartiteness is to try 2-coloring the graph using BFS. Pick any uncolored node, assign it color 0, and put it in a queue. Then process the queue: for each node, look at all its neighbors. If a neighbor hasn't been colored yet, assign it the opposite color and add it to the queue. If a neighbor is already colored with the same color as the current node, we've found a conflict, and the graph isn't bipartite.

Why BFS specifically? BFS explores nodes level by level. In a bipartite graph, all nodes at even levels get one color, and all nodes at odd levels get the other. This layer-by-layer exploration maps perfectly to the alternating color assignment we need.

Since the graph might be disconnected, we loop through all nodes and kick off a BFS from any node that hasn't been colored yet. If every component passes the 2-coloring check, the graph is bipartite.

Algorithm

  1. Create a color array of size n, initialized to -1 (uncolored).
  2. For each node from 0 to n-1:
    • If the node is already colored, skip it.
    • Otherwise, assign it color 0 and add it to a BFS queue.
  3. Process the BFS queue:
    • Dequeue a node u.
    • For each neighbor v of u:
      • If v is uncolored, assign it 1 - color[u] (the opposite color) and enqueue it.
      • If v already has the same color as u, return false.
  4. If we process all nodes without conflict, return true.

Example Walkthrough

1Initial graph. color = [-1, -1, -1, -1]. Start BFS from node 0.
0132
1/7
1All nodes uncolored (-1)
0
-1
1
-1
2
-1
3
-1
1/7

Code

BFS is already optimal at O(V + E), but DFS offers a recursive alternative that some find more elegant. Let's see how the same coloring logic works with depth-first traversal.

Approach 2: DFS (Graph Coloring)

Intuition

The DFS approach uses the exact same coloring logic, just with a different traversal strategy. Instead of exploring level by level, we dive deep along one path, coloring as we go, and backtrack when we hit a dead end or a conflict.

The recursive structure makes the code quite clean: color the current node, then recursively try to color all uncolored neighbors with the opposite color. If any recursive call finds a conflict, propagate the failure upward.

Some people find DFS easier to reason about because the recursion naturally handles the "try one path, then backtrack" pattern. Others prefer BFS because the iterative queue is more explicit. Both are equally valid in an interview.

Algorithm

  1. Create a color array of size n, initialized to -1 (uncolored).
  2. For each node from 0 to n-1:
    • If the node is already colored, skip it.
    • Otherwise, start a DFS from this node with color 0.
  3. In the DFS function:
    • Assign the current node its color.
    • For each neighbor of the current node:
      • If the neighbor is uncolored, recursively DFS with the opposite color. If the recursive call returns false, return false.
      • If the neighbor already has the same color, return false.
    • If all neighbors are compatible, return true.
  4. If all components pass, return true.

Example Walkthrough

1Initial graph. All nodes uncolored. Start DFS from node 0.
0123
1/5
1All nodes uncolored (-1)
0
-1
1
-1
2
-1
3
-1
1/5

Code

Both BFS and DFS are optimal at O(V + E). Union Find offers a completely different perspective: instead of coloring nodes, we group neighbors together and check for contradictions.

Approach 3: Union Find

Intuition

Here's a completely different way to think about bipartiteness. Instead of coloring, think about grouping. For a bipartite graph, every node's neighbors must all belong to the opposite partition. That means all neighbors of a node should be in the same set as each other (just not in the same set as the node itself).

Union Find gives us exactly the machinery to track these groupings. For each node u, we union all of u's neighbors together (they must all be in the same partition). Then we check: is u in the same set as any of its neighbors? If yes, we have a contradiction, and the graph isn't bipartite.

This approach is a bit less intuitive than graph coloring, but it's a good demonstration of Union Find skills, which interviewers love to see.

Algorithm

  1. Initialize a Union Find structure with n nodes.
  2. For each node u from 0 to n-1:
    • If u has no neighbors, skip it.
    • Union all neighbors of u together (they must be in the same partition).
    • Check if u and its first neighbor are in the same set. If yes, return false.
  3. If no conflicts found, return true.

Example Walkthrough

1Initial: each node is its own parent. parent = [0, 1, 2, 3]
{ "nodes": [ 0, 1, 2, 3 ], "parents": [ 0, 1, 2, 3 ] }
1/6

Code