Is Graph Bipartite? — Solution

Problem

Given an undirected graph represented as an adjacency list, determine whether its vertices can be split into two groups such that every edge connects a vertex in one group to a vertex in the other — no two neighbors may belong to the same group. This is equivalent to asking whether the graph can be 2-colored.

For example, a square (four nodes connected in a cycle) is bipartite:

• Input: graph = [[1,3],[0,2],[1,3],[0,2]]
• Output: true
• Explanation: Assign nodes 0 and 2 to group A and nodes 1 and 3 to group B — every edge crosses between the two groups.

A triangle, however, is not bipartite because three mutually connected nodes cannot be 2-colored without a conflict:

• Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
• Output: false
• Explanation: Nodes 0, 1, and 2 form a triangle (an odd-length cycle), which cannot be split into two groups.

Intuition

A graph is bipartite if and only if it contains no cycle of odd length. Rather than searching for odd cycles directly, we can detect them by attempting to 2-color the graph: assign color 0 to a starting node, then force every neighbor to take color 1, and so on. If we ever encounter a neighbor that already carries the same color as the current node, we've found an odd cycle and the graph cannot be bipartite. Because the graph may be disconnected, we must repeat this check from every unvisited node.

Solution — BFS 2-Coloring

Treat colors as group membership (0 or 1) and propagate them across the graph with BFS, flipping the color at each hop. Use a sentinel value (-1) for unvisited nodes so we can distinguish them from either color group.

1. Create a color array of length n initialized to -1 (unvisited).
2. For each node that hasn't been colored yet, start a BFS from that node with color 0.
3. For each neighbor of the current node, if unvisited assign the opposite color and enqueue it.
4. If the neighbor is already colored and shares the current node's color, return false immediately.
5. Complete BFS for this component without conflict.
6. After checking all components, return true.

1from collections import deque
2from typing import List
3
4def isBipartite(graph: List[List[int]]) -> bool:
5    n = len(graph)
6    color = [-1] * n  # -1 means unvisited; 0 and 1 are the two groups
7
8    for start in range(n):
9        if color[start] != -1:
10            continue  # already processed as part of an earlier component
11
12        queue = deque([start])
13        color[start] = 0
14
15        while queue:
16            node = queue.popleft()
17            for neighbor in graph[node]:
18                if color[neighbor] == -1:
19                    color[neighbor] = 1 - color[node]  # force the opposite group
20                    queue.append(neighbor)
21                elif color[neighbor] == color[node]:
22                    return False  # same color on both ends of an edge — odd cycle
23
24    return True

Time: O(V + E) — every node and edge is visited at most once across all BFS traversals.

Space: O(V) — the color array and BFS queue each hold at most V entries.

Complexity Summary

Common Mistakes

• Starting BFS from only node 0 — the graph may be disconnected, so components not reachable from node 0 are never checked. The outer loop over all start values is essential, not optional.
• Initializing color to 0 instead of -1 — using 0 as both "unvisited" and "group A" makes it impossible to tell whether a node has been colored or just happens to be in group A; always use a third sentinel value (-1) for unvisited.
• Skipping already-visited neighbors entirely — when you encounter a neighbor that's already colored, you must still compare its color to the current node's; skipping it silently misses the conflict check that catches odd cycles.
• Confusing the adjacency list format — graph[i] gives the list of neighbors for node i as direct indices, not weights or objects; iterating for neighbor in graph[node] is correct, not graph[node][i] as if it were a 2D matrix.
• Treating the outer loop as redundant — if every BFS returns without conflict but you only checked one component, you've only proven that one component is bipartite. Each disconnected piece must pass independently.

Related Problems

• Number of Islands — BFS/DFS from each unvisited cell to explore a connected component, same outer-loop pattern
• Course Schedule — graph cycle detection using topological sort on a directed graph
• Clone Graph — BFS traversal that visits every node exactly once
• Rotting Oranges — multi-source BFS where state propagates across edges in waves
• Find if Path Exists in Graph — fundamental graph reachability using the same BFS skeleton