AlgoMaster Logo

Is Graph Bipartite?

mediumFrequency8 min readUpdated June 23, 2026

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 graph bipartiteness problem, and it shows up in scheduling, matching, and conflict resolution.

A graph is bipartite if and only if it contains no odd-length cycle. Try to 2-color a cycle of length 3 (a triangle): node A gets color 0, B gets 1, C must differ from B so it gets 0, but C is also adjacent to A which is already 0, so two adjacent nodes share a color. A cycle of length 4 alternates cleanly: 0, 1, 0, 1.

So the problem reduces to a coloring question: 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 reach a node whose neighbor already holds the same color, it is not.

The graph may be disconnected, so we check every connected component independently. The graph is bipartite only if all of its components are.

Key Constraints:

  • 1 <= n <= 100: The graph is small, so any of these approaches runs instantly. The standard BFS/DFS approach is already O(V + E), which is optimal regardless.
  • 0 <= graph[u].length < n: A node can have up to n-1 neighbors, so the graph can be dense, with E up to roughly n^2. The coloring approaches scale with V + E, so density does not hurt them.
  • The graph may be disconnected, so we iterate over all nodes and start a fresh traversal from any node not yet colored.

Approach 1: BFS (Graph Coloring)

Intuition

We check bipartiteness by 2-coloring the graph with 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 has not been colored yet, assign it the opposite color and add it to the queue. If a neighbor already holds the same color as the current node, the graph has an odd cycle and is not bipartite.

BFS suits this well because it explores nodes level by level. In a bipartite graph, nodes at even distance from the start take one color and nodes at odd distance take the other, so the layer-by-layer order matches the alternating color assignment.

Because the graph may be disconnected, we loop through all nodes and start a BFS from any node that has not been colored. 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

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

Code

BFS is optimal at O(V + E). The same coloring logic also works with depth-first traversal, which expresses the recursion more compactly.

Approach 2: DFS (Graph Coloring)

Intuition

The DFS approach uses the same coloring logic with a different traversal order. Instead of exploring level by level, we follow one path as deep as it goes, coloring as we descend, and return up the call stack when a path is exhausted or a conflict appears.

The recursive structure keeps the code compact: color the current node, then recursively color each uncolored neighbor with the opposite color. If any recursive call reports a conflict, return false up the chain.

Traversal order does not affect correctness here. What matters is that every node gets colored and every edge gets checked, and both BFS and DFS guarantee that. The one practical difference is depth: a graph shaped like a long chain forces recursion as deep as the chain. With n capped at 100, that is well within the stack limit.

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

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

Code

Both BFS and DFS are optimal at O(V + E). The next approach takes a different angle: instead of coloring nodes, it groups neighbors together and checks for contradictions.

Approach 3: Union Find

Intuition

Bipartiteness can also be framed as grouping rather than coloring. In a bipartite graph, every node's neighbors all belong to the opposite partition, which means all the neighbors of a single node belong to the same partition as each other, distinct from the node itself.

Union Find tracks these groupings. For each node u, we union all of u's neighbors together, since they must share a partition. Then we check whether u lands in that same set. If it does, the constraints have forced a node and its neighbor into one partition, which is a contradiction, so the graph is not bipartite.

This view is less direct than coloring, but it solves the problem using only set membership and merging.

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