Community Problem
Is Graph Bipartite?
Difficulty: Medium
Decide whether an undirected graph admits a 2-coloring with no edge sharing a color, using BFS over each component.
Is Graph Bipartite?
Decide whether an undirected graph admits a 2-coloring with no edge sharing a color, using BFS over each component.
By CodeSnatch
February 26, 2026
·
Updated May 18, 2026
975 views
3
4.5 (17)
I had this on a Meta phone screen, and the conversation that followed the BFS was the actual signal: the interviewer wanted me to articulate WHY two-coloring works (no odd cycles) and what happens with disconnected components (you have to start a fresh BFS from every uncolored vertex). The catalog covers BFS but skipped this foundational two-coloring problem. The official version of this entry, that is.
Is Graph Bipartite?
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between u and v. The graph has the following properties:
- There are no self-edges (
graph[u]does not containu). - There are no parallel edges.
- If
vis ingraph[u], thenuis ingraph[v](the graph is undirected). - The graph may not be connected, meaning there may be two nodes
uandvsuch that there is no path between them.
A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B. Return true if and only if it is bipartite.
Examples
Example 1:
- Input:
graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]] - Output:
false - Explanation: There is a triangle
0 - 1 - 2 - 0, an odd cycle, so two-coloring is impossible.
Example 2:
- Input:
graph = [[1, 3], [0, 2], [1, 3], [0, 2]] - Output:
true - Explanation: The graph is a 4-cycle
0 - 1 - 2 - 3 - 0. Color{0, 2}as A and{1, 3}as B. Every edge is between A and B.
Example 3:
- Input:
graph = [[]] - Output:
true - Explanation: An isolated vertex is trivially bipartite.
Example 4:
- Input:
graph = [[1], [0], [3], [2]] - Output:
true - Explanation: Two disconnected edges. Each component is bipartite. The whole graph is bipartite.
Constraints
graph.length == n.1 <= n <= 100.0 <= graph[u].length < n.0 <= graph[u][i] <= n - 1.graph[u]does not containu.- All the values of
graph[u]are unique. - The graph is undirected: if
graph[u]containsv, thengraph[v]containsu.
Follow-up
Why is BFS two-coloring equivalent to "no odd cycle"? An odd cycle forces some vertex to be both colors at once during BFS. Conversely, if there is no odd cycle, BFS levels alternate cleanly between the two colors and the coloring is consistent.
Solution
Hints
Solution Walkthrough
Approach: BFS Two-Coloring Per Component (O(V + E) time, O(V) space)
A graph is bipartite iff it has no odd cycles. The cleanest constructive check is to BFS the graph and try to two-color it. Start each component's BFS by coloring the source vertex 0. For every neighbor of the current vertex:
- If uncolored, assign the OPPOSITE color and enqueue.
- If already colored the SAME color as the current vertex, the graph is not bipartite (this edge cannot be 2-colored).
- If already colored the OPPOSITE color, no action needed.
For disconnected graphs, restart BFS from any uncolored vertex.
Algorithm
- Allocate
color[0..n-1]initialized to-1. - For
start = 0..n-1:- If
color[start] != -1, skip (this component is already done). - Set
color[start] = 0. Enqueuestart. - BFS: dequeue
u; for each neighborv:- If
color[v] == -1:color[v] = 1 - color[u]; enqueue. - Else if
color[v] == color[u]: returnfalse.
- If every component finishes consistently, return
true.
Why It Works (DFS Equivalence)
DFS gives the same result. The core invariant is the same: "adjacent vertices must have opposite colors". BFS levels alternate cleanly between the two colors when no odd cycle exists. DFS does the same with a recursion stack instead of a queue. Both detect conflicts at the moment they revisit a colored vertex with the wrong color. We use BFS here because the iterative loop avoids deep recursion on long graph paths and reads cleanly.
Complexity
Sample bipartition
Graph 4-cycle: 0 - 1 - 2 - 3 - 0
BFS from 0:
Color 0 = A
Visit 1, 3 -> color them B
Visit 2 from 1 -> color it A
Visit 2 from 3 -> already A, parent B, OK
Result: A = {0, 2}, B = {1, 3}.Metric Value
Time O(V + E) - each vertex enqueued at most once, each edge inspected twice
Space O(V) for the color array and the BFS queuePitfalls
- Forgetting disconnected components. A bipartite check that BFS-only-from-zero will incorrectly miss conflicts in components not connected to vertex 0. Loop over every uncolored start.
- Using a single boolean visited flag. A
visitedflag is not enough; you need the COLOR (two-valued) to detect conflicts. Use-1 / 0 / 1or two separate sets. - Recursive DFS on adversarial input. Long path graphs can hit stack limits. The iterative BFS shown here is depth-safe.
Solution Code