A graph is bipartite if we can divide its vertices into two groups such that no edge connects two vertices from the same group.

Equivalent view:

We can color every vertex using 2 colors so that adjacent vertices always have different colors.

Core Idea

Suppose we use:

+1 → Color A
-1 → Color B
 0 → Uncolored

For every edge:

u — v

we require:

color[u] != color[v]

If a neighbor is uncolored:

color[neighbor] = -color[node];

If a neighbor already has the same color:

return false;

Mental Trigger

“Can I divide the graph into 2 groups?” → 2-Coloring → Bipartite

Another important trigger:

Odd cycle → Not Bipartite

For an undirected graph:

Bipartite ⇔ No odd-length cycle

Pattern Table

Pattern	Typical Questions	Trigger
BFS Coloring	Check bipartite	Two-color assignment
DFS Coloring	Alternative approach	Recursive coloring
Conflict Detection	Invalid coloring	Same-color neighbor
Multi-Component	Disconnected graph	Check every component
Odd Cycle	Detect impossibility	Odd-length cycle

1. Generic Bipartite BFS Template (Base)

This is the main template to memorize.

Watch a 2-coloring BFS succeed on the square… then fail the moment the chord creates an odd cycle:

Bipartite Check (2-Coloring)

Decide whether a graph's vertices split into two independent sets.

BFS/DFS 2-color from a start; every neighbour must get the opposite color. If an edge ever joins two same-colored nodes, an odd cycle exists and the graph is NOT bipartite. Bipartite ⟺ no odd cycle.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        color[start] = RED; queue = [start]
                      
                        2
                        while queue not empty:
                      
                        3
                          n = queue.poll()
                      
                        4
                          for each neighbour m:
                      
                        5
                            if color[m] unset: color = OPPOSITE; queue.add(m)
                      
                        6
                            else if color[m] == color[n]: NOT BIPARTITE

public boolean isBipartite(List<List<Integer>> graph) {
    int n = graph.size();

    // 0 = uncolored
    // 1 = color A
    // -1 = color B
    int[] color = new int[n];

    Queue<Integer> queue = new LinkedList<>();

    for (int i = 0; i < n; i++) {

        // Already belongs to a processed component
        if (color[i] != 0) {
            continue;
        }

        // Start a new component
        color[i] = 1;
        queue.offer(i);

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : graph.get(node)) {

                // Assign opposite color
                if (color[neighbor] == 0) {
                    color[neighbor] = -color[node];
                    queue.offer(neighbor);
                }

                // Same color on both ends → conflict
                else if (color[neighbor] == color[node]) {
                    return false;
                }
            }
        }
    }

    return true;
}

from collections import deque

def is_bipartite(graph):
    n = len(graph)

    # 0 = uncolored, 1 = color A, -1 = color B
    color = [0] * n

    queue = deque()

    for i in range(n):

        # Already belongs to a processed component
        if color[i] != 0:
            continue

        # Start a new component
        color[i] = 1
        queue.append(i)

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:

                # Assign opposite color
                if color[neighbor] == 0:
                    color[neighbor] = -color[node]
                    queue.append(neighbor)

                # Same color on both ends → conflict
                elif color[neighbor] == color[node]:
                    return False

    return True

bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();

    // 0 = uncolored, 1 = color A, -1 = color B
    vector<int> color(n, 0);

    queue<int> q;

    for (int i = 0; i < n; i++) {

        // Already belongs to a processed component
        if (color[i] != 0) {
            continue;
        }

        // Start a new component
        color[i] = 1;
        q.push(i);

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int neighbor : graph[node]) {

                // Assign opposite color
                if (color[neighbor] == 0) {
                    color[neighbor] = -color[node];
                    q.push(neighbor);
                }

                // Same color on both ends → conflict
                else if (color[neighbor] == color[node]) {
                    return false;
                }
            }
        }
    }

    return true;
}

function isBipartite(graph) {
  const n = graph.length;

  // 0 = uncolored, 1 = color A, -1 = color B
  const color = new Array(n).fill(0);

  // ponytail: shift() is O(n), fine at this scale; use head-index deque if profiling matters
  const queue = [];

  for (let i = 0; i < n; i++) {
    // Already belongs to a processed component
    if (color[i] !== 0) {
      continue;
    }

    // Start a new component
    color[i] = 1;
    queue.push(i);

    while (queue.length > 0) {
      const node = queue.shift();

      for (const neighbor of graph[node]) {
        // Assign opposite color
        if (color[neighbor] === 0) {
          color[neighbor] = -color[node];
          queue.push(neighbor);
        }
        // Same color on both ends → conflict
        else if (color[neighbor] === color[node]) {
          return false;
        }
      }
    }
  }

  return true;
}

Everything else in bipartite problems is usually a modification of this coloring idea.

Pattern 1: Basic Bipartite Check

What are we checking?

We want:

Every edge connects different colors

Example:

1 ----- 2
|       |
|       |
4 ----- 3

One valid coloring is:

1 = A
2 = B
3 = A
4 = B

Every edge connects:

A ↔ B

So the graph is bipartite.

What Changed from Generic BFS?

1. Replace `visited[]` with `color[]`

Normal BFS:

boolean[] visited = new boolean[n];

Bipartite BFS:

int[] color = new int[n];

because we need more information than just:

“Have I seen this node?”

We need:

“Which group does this node belong to?“

2. Assign the opposite color

Added:

color[neighbor] = -color[node];

If:

node = A

then:

neighbor = B

and vice versa.

3. Detect conflicts

Added:

if (color[neighbor] == color[node]) {
    return false;
}

This means:

A — A   ❌
B — B   ❌

Bipartite BFS = BFS + 2-coloring + conflict detection

Pattern 2: Multi-Component Bipartite Graph

A graph may contain multiple disconnected components:

Starting BFS only from 1 would never visit 4, 5, or 6.

Therefore:

for (int i = 0; i < n; i++) {
    if (color[i] == 0) {
        // Start a new component
    }
}

What Changed from Basic BFS?

Added outer loop

for (int i = 0; i < n; i++) {
    if (color[i] != 0) {
        continue;
    }

    color[i] = 1;
    queue.offer(i);
}

Every uncolored node starts a new component.

Disconnected graph → start coloring from every uncolored vertex.

Pattern 3: DFS Bipartite Check

The exact same coloring rule works with DFS.

Java Code

public boolean isBipartiteDFS(List<List<Integer>> graph) {
    int n = graph.size();

    int[] color = new int[n];

    for (int i = 0; i < n; i++) {

        if (color[i] == 0) {

            if (!dfs(graph, i, 1, color)) {
                return false;
            }
        }
    }

    return true;
}

private boolean dfs(
        List<List<Integer>> graph,
        int node,
        int currentColor,
        int[] color) {

    color[node] = currentColor;

    for (int neighbor : graph.get(node)) {

        // Assign opposite color
        if (color[neighbor] == 0) {

            if (!dfs(
                    graph,
                    neighbor,
                    -currentColor,
                    color)) {

                return false;
            }
        }

        // Conflict
        else if (color[neighbor] == color[node]) {
            return false;
        }
    }

    return true;
}

def is_bipartite_dfs(graph):
    n = len(graph)

    color = [0] * n

    for i in range(n):

        if color[i] == 0:

            if not dfs(graph, i, 1, color):
                return False

    return True

def dfs(graph, node, current_color, color):
    color[node] = current_color

    for neighbor in graph[node]:

        # Assign opposite color
        if color[neighbor] == 0:

            if not dfs(
                graph,
                neighbor,
                -current_color,
                color
            ):
                return False

        # Conflict
        elif color[neighbor] == color[node]:
            return False

    return True

bool dfs(
        vector<vector<int>>& graph,
        int node,
        int currentColor,
        vector<int>& color) {

    color[node] = currentColor;

    for (int neighbor : graph[node]) {

        // Assign opposite color
        if (color[neighbor] == 0) {

            if (!dfs(
                    graph,
                    neighbor,
                    -currentColor,
                    color)) {

                return false;
            }
        }

        // Conflict
        else if (color[neighbor] == color[node]) {
            return false;
        }
    }

    return true;
}

bool isBipartiteDFS(vector<vector<int>>& graph) {
    int n = graph.size();

    vector<int> color(n, 0);

    for (int i = 0; i < n; i++) {

        if (color[i] == 0) {

            if (!dfs(graph, i, 1, color)) {
                return false;
            }
        }
    }

    return true;
}

function isBipartiteDFS(graph) {
  const n = graph.length;

  const color = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    if (color[i] === 0) {
      if (!dfs(graph, i, 1, color)) {
        return false;
      }
    }
  }

  return true;
}

function dfs(graph, node, currentColor, color) {
  color[node] = currentColor;

  for (const neighbor of graph[node]) {
    // Assign opposite color
    if (color[neighbor] === 0) {
      if (!dfs(graph, neighbor, -currentColor, color)) {
        return false;
      }
    }
    // Conflict
    else if (color[neighbor] === color[node]) {
      return false;
    }
  }

  return true;
}

What Changed from BFS?

Queue → Recursion

BFS:

Queue<Integer> queue;

DFS:

dfs(graph, neighbor, -currentColor, color);

Level processing → Recursive propagation

BFS spreads:

level 0
   ↓
level 1
   ↓
level 2

DFS follows:

node
 ↓
neighbor
 ↓
neighbor
 ↓
backtrack

But the coloring rule remains identical:

color[neighbor] = -color[node];

BFS and DFS are just traversal strategies. The bipartite rule stays the same.

Pattern 4: Odd Cycle Detection

This is one of the most important insights.

For an undirected graph:

A graph is bipartite if and only if it contains no odd-length cycle.

Consider:

    1
   / \
  2---3

This is a cycle of length 3.

Try coloring:

1 = A
2 = B
3 = B

But there is an edge:

2 — 3

connecting the same color.

Conflict:

B — B ❌

Therefore:

Triangle → Not Bipartite

What Changed from the Base Template?

Nothing special needs to be added.

The coloring conflict automatically detects the odd cycle.

else if (color[neighbor] == color[node]) {
    return false;
}

2-coloring conflict = odd cycle exists.

Pattern 5: Self-Loop Detection

A self-loop is an immediate contradiction:

1
↺

The edge is:

1 — 1

The same vertex would need to have a different color from itself.

Therefore:

Self-loop → Not Bipartite

The generic coloring algorithm detects this automatically because:

color[neighbor] == color[node]

when:

neighbor == node

A self-loop makes an undirected graph non-bipartite.

Pattern Evolution

Base BFS
    ↓
Replace visited[] with color[]
    ↓
Assign opposite color
    ↓
Detect same-color conflict
    ↓
Handle disconnected components
    ↓
DFS alternative
    ↓
Odd-cycle detection

Visual Intuition

Consider:

1 — 2 — 3 — 4

Start:

1 = A

Then:

2 = B

because it is adjacent to 1.

Then:

3 = A

Then:

4 = B

So:

A: {1, 3}
B: {2, 4}

No edge connects two nodes in the same group.

Therefore:

Bipartite ✅

Add One More Edge

Suppose we add:

1 — 3

But:

1 = A
3 = A

Now:

A — A

Conflict.

Therefore:

Not Bipartite ❌

And notice:

1 → 2 → 3 → 1

is an odd cycle.

Common Mistakes

Using `boolean[] visited`

Wrong:

boolean[] visited = new boolean[n];

A normal visited array only tells us:

visited / not visited

Bipartite checking needs:

uncolored / color A / color B

Use:

int[] color = new int[n];

Coloring after enqueueing

Do not wait until the node is removed from the queue.

Correct:

color[neighbor] = -color[node];
queue.offer(neighbor);

The color must be assigned when the node is discovered.

Forgetting disconnected components

Wrong:

bfs(graph, 0);

This only checks the component containing node 0.

Correct:

for (int i = 0; i < n; i++) {
    if (color[i] == 0) {
        // Start BFS/DFS
    }
}

Assuming every graph can be bipartitioned

A triangle:

1
|\
| \
2--3

cannot be divided into two independent sets.

Always check for conflicts.

Confusing bipartite with directed graph coloring

The standard bipartite definition applies to undirected graphs.

For directed graphs, problems involving coloring or constraints may require a different interpretation.

Complexity

For an adjacency-list graph:

Time:  O(V + E)
Space: O(V)

Every vertex and edge is processed a constant number of times.

For DFS, the recursion stack can also reach:

O(V)

in the worst case.

Recognition Cheat Sheet

If you see…	Think…
”Divide nodes into 2 groups”	Bipartite
”Two teams”	Bipartite
”Two colors”	Bipartite
”Adjacent nodes must differ”	Bipartite
”No enemies on same team”	Bipartite
”Odd cycle”	Not Bipartite
”Check graph coloring”	Bipartite
Disconnected graph	Check every component

Common Interview Problems

LeetCode

Bipartite vs Normal Graph Traversal

Normal BFS/DFS	Bipartite BFS/DFS
`visited[]`	`color[]`
Visit nodes	Assign groups
Avoid revisiting	Enforce opposite colors
Traversal problem	Constraint problem
No color conflict	Same-color edge = failure

Earn Premium with Referrals

Core Idea

Mental Trigger

Pattern Table

1. Generic Bipartite BFS Template (Base)

Bipartite Check (2-Coloring)

Pattern 1: Basic Bipartite Check

What are we checking?

What Changed from Generic BFS?

1. Replace visited[] with color[]

2. Assign the opposite color

3. Detect conflicts

Pattern 2: Multi-Component Bipartite Graph

What Changed from Basic BFS?

Added outer loop

Pattern 3: DFS Bipartite Check

Java Code

What Changed from BFS?

Queue → Recursion

Level processing → Recursive propagation

Pattern 4: Odd Cycle Detection

What Changed from the Base Template?

Pattern 5: Self-Loop Detection

Pattern Evolution

Visual Intuition

Add One More Edge

Common Mistakes

Using boolean[] visited

Coloring after enqueueing

Forgetting disconnected components

Assuming every graph can be bipartitioned

Confusing bipartite with directed graph coloring

Complexity

Recognition Cheat Sheet

Common Interview Problems

LeetCode

Bipartite vs Normal Graph Traversal

Premium Content

My Private Notes

1. Replace `visited[]` with `color[]`

Using `boolean[] visited`