← DSA Atlas
Dedicated problem page · #785

Is Graph Bipartite?

MediumGraph DFS and BFSTwo-coloring / 2-partition checkBFS graph coloring
Solve on LeetCode ↗
785
MediumGraph DFS and BFSBFS graph coloringTwo-coloring / 2-partition check

Is Graph Bipartite?

Given an undirected graph as an adjacency list (graph[u] lists the neighbors of node u), decide whether it is bipartite — whether the nodes can be split into two sets so that every edge connects a node in one set to a node in the other. Return true if such a split exists.

Open official problem prompt ↗
In plain English

Determine whether the graph's nodes admit a red/blue labeling in which no edge joins two nodes of the same color.

Picture it like this

Seat rivals at a two-sided table: each person must sit across from everyone they conflict with. If you can seat everyone with all rivalries spanning the table, it works; if two rivals are forced onto the same side, it is impossible.

Example
Input
graph = [[1,3],[0,2],[1,3],[0,2]]
Output
true
Why
Coloring nodes {0,2} one color and {1,3} the other leaves every edge between the two colors, so the graph is bipartite.
Constraints
graph.length == n1 <= n <= 1000 <= graph[u].length < n0 <= graph[u][i] <= n - 1The graph is undirected and has no self-edges or parallel edgesIt may be disconnected
Pattern lesson

See the pattern, then code

Two-coloring / 2-partition check
Recognition clue

The prompt asks to split nodes into two groups with all edges crossing between groups — the definition of bipartite. Any question about 2-colorability or 'no odd cycle' maps to a BFS/DFS coloring check.

↗
Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. A graph is bipartite exactly when you can 2-color it so adjacent nodes differ. Color a start node, force every neighbor to the opposite color, and propagate. A conflict (a neighbor that already has the same color) proves an odd cycle and kills bipartiteness.

New words, made simpleKnow these before the algorithm
Bipartite
Nodes split into two sets with every edge going between the sets.
2-coloring
Assigning one of two colors to each node so adjacent nodes differ.
Odd cycle
A cycle with an odd number of edges — the exact obstruction to bipartiteness.
Component
A maximal connected piece; each is colored independently.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try all 2^n partitions

Exponential and needless — coloring is forced once one node is fixed.

Enumerate every way to split nodes into two sets and test edges.

Time O(2^n * E)Space O(n)
Best choiceBFS/DFS 2-coloring

Linear and complete; detects the odd cycle that blocks bipartiteness.

Color a start node, force neighbors opposite, propagate, and fail on a same-color edge.

Time O(V + E)Space O(V)
The rule we keep true

Invariant

Every colored node's color is the opposite of each already-colored neighbor along the traversal tree; a violation is detected the moment it would occur.

Why this is correct

Reasoning

Once a start node's color is fixed, each other node's color in its component is forced by parity of distance. If propagation is always consistent the component is bipartite; a same-color edge means two nodes at the same parity are adjacent, i.e. an odd cycle exists, which is impossible in a bipartite graph. Looping over all start nodes handles disconnected components.

The algorithm in three movesSay these aloud before coding
1Keep a color map; iterate every node to cover disconnected components

color = {0:0}

2For an uncolored node, color it 0 and BFS from it

0 -> neighbors 1,3 get color 1

3For each neighbor, if uncolored assign the opposite color and enqueue

1 -> neighbor 2 gets color 0

4If a neighbor already shares the current node's color, return false

no same-color edge found -> true

5If all components color cleanly, return true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
0:A0
1:B1
2:A2
3:B3
1 · Readnode 0 uncolored
2 · AskAssign a color?
3 · Update statecolor={0:0}, queue=[0]
4 · ResultNode 0 colored 0.
Key takeaway

Nodes 0 and 2 take color A, nodes 1 and 3 take color B; every edge crosses colors.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-9Component loop and seeding

    Iterating every index and skipping already-colored nodes ensures disconnected components are each colored.

  2. 2
    Lines 13-17Propagate opposite color

    color[node] ^ 1 flips between 0 and 1, enforcing the alternating rule for uncolored neighbors.

  3. 3
    Lines 18-19Conflict detection

    A neighbor already sharing this node's color reveals an odd cycle, so the graph cannot be bipartite.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single node with no edges -> trivially bipartite (true)
  • Disconnected graph where some components are bipartite and one is not -> false
  • A triangle (odd cycle) -> false
  • Nodes with empty adjacency lists -> still colored, no conflicts
!

Common beginner mistakes

  • Coloring only from node 0 and missing other components in a disconnected graph
  • Using a visited boolean instead of a color, losing the ability to compare colors on edges
  • Assuming the graph is connected
  • Off-by-one confusion mutating color with arithmetic instead of XOR, e.g. 1 - color occasionally miswritten
Check your understanding

What structural feature of a graph guarantees it is NOT bipartite, and how does the coloring detect it?

More in Graph DFS and BFS

#200Number of IslandsGrid flood fill#133Clone GraphGraph traversal with clone map#994Rotting OrangesMulti-source BFS (level-by-level)#127Word LadderShortest transformation via BFS#130Surrounded RegionsBorder-guarded flood fill#286Walls and GatesMulti-source BFS distance fill