Bipartite check

A four-node cycle: 0-1-2-3-0. Color node 0 red. Its neighbor 1 must be blue. Vertex 2, adjacent to 1, has to be red. Walking back to vertex 3, adjacent to 2, forces blue. The closing edge 3-0 lands across the partition. Every edge crosses; the graph is bipartite.

Now make it a triangle: 0-1-2-0. Color 0 red, 1 blue, 2 red. The closing edge is 0-2, both red. Two-coloring fails on the third edge. This graph is not bipartite, and the only thing wrong with it is the cycle’s length: three is odd. That observation is the chapter.

Locating this pattern

flowchart TD
    A[Problem says<br/>two groups / two factions /<br/>two-color the graph] --> B{Graph type?}
    B -- Undirected --> C{What's the question?}
    B -- Directed --> D[Topological sort,<br/>not bipartite check]
    C -- Can it split? --> E[BFS 2-coloring<br/>this chapter]
    C -- Find the matching --> F[Bipartite matching<br/>different chapter]
    C -- k groups, k >= 3 --> G{Degree bounded?}
    G -- Yes, k > Delta --> H[Greedy k-coloring<br/>see §When the pattern bends]
    G -- No --> I[NP-complete in general]

Why the obvious approach wastes most of its work

The first instinct on bipartite check is to enumerate. Try every assignment of vertices to two sides. Reject the assignment if any edge stays inside one side. Return whether any assignment survives.

# Brute force: O(2^n * E), what we're replacing
def is_bipartite_brute(graph):
    n = len(graph)
    for mask in range(1 << n):
        # bit i of mask = which side vertex i is on
        ok = True
        for u in range(n):
            for v in graph[u]:
                if ((mask >> u) & 1) == ((mask >> v) & 1):
                    ok = False
                    break
            if not ok:
                break
        if ok:
            return True
    return False

Two reasons this is the wrong answer. First, the running time is exponential in n; LC 785’s cap of n ≤ 100 already gives 2^100 assignments, more than the atoms in the visible universe. Second, the algorithm has no idea why an assignment fails. It just iterates.

The fix is a single pass that builds the partition while it walks. Color the first vertex either side, push it onto a queue, and for every edge you cross, paint the other endpoint the opposite color. If you ever see an edge whose endpoints are already painted the same color, give up: that edge is the proof no 2-coloring exists. If you finish the walk without a conflict, the colors you assigned are the partition.

The trick is that “no 2-coloring exists” has a much sharper characterization than the brute force suggests. A graph is bipartite if and only if it has no odd-length cycle.¹ König proved this in 1916; the proof is short, the consequence is sweeping. BFS happens to detect odd cycles for free. When you walk a tree-like region, every edge points from one BFS level to the next, alternating colors trivially. The only way an edge can violate the alternation is to close a cycle, and the only cycles that violate are the odd ones, because in an even cycle the colors swap an even number of times and end where they started.

The pattern

Two phases nested. The outer loop visits every vertex at least once so disconnected components don’t slip through. For each starting vertex that hasn’t been colored yet, run BFS and paint as you go.

from collections import deque


def is_bipartite(graph):
    n = len(graph)
    color = [0] * n                       # 0 = unvisited, 1 / -1 = the two color classes
    for start in range(n):
        if color[start] != 0:
            continue                      # already painted by a prior component
        color[start] = 1
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == 0:
                    color[v] = -color[u]  # flip color across the edge
                    q.append(v)
                elif color[v] == color[u]:
                    return False          # same-color edge: odd cycle
    return True

# LC 785. Is Graph Bipartite?
from collections import deque
from typing import List


def is_bipartite(graph: List[List[int]]) -> bool:
    """LC 785: true iff `graph` admits a 2-coloring (no odd cycle)."""
    n = len(graph)
    color = [0] * n                       # 0 = unvisited, 1 / -1 = the two color classes
    for start in range(n):
        if color[start] != 0:
            continue                      # already painted by a prior component
        color[start] = 1
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == 0:
                    color[v] = -color[u]  # flip color across the edge
                    q.append(v)
                elif color[v] == color[u]:
                    return False          # same-color edge: odd cycle
    return True

// LC 785. Is Graph Bipartite?
import java.util.*;

public class Sol {
    public static boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];                 // 0 = unvisited, 1 / -1 = two color classes
        for (int start = 0; start < n; start++) {
            if (color[start] != 0) continue;       // skip already-colored components
            color[start] = 1;
            Deque<Integer> q = new ArrayDeque<>(); // ArrayDeque per code-idioms.md §2.5
            q.offer(start);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph[u]) {
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        q.offer(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

// LC 785. Is Graph Bipartite?
#include <vector>
#include <queue>

class Solution {
public:
    bool isBipartite(std::vector<std::vector<int>>& graph) {
        int n = (int)graph.size();
        std::vector<int> color(n, 0);          // 0 = unvisited, 1 / -1 = two classes
        for (int start = 0; start < n; ++start) {
            if (color[start] != 0) continue;
            color[start] = 1;
            std::queue<int> q;
            q.push(start);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : graph[u]) {
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

// LC 785. Is Graph Bipartite?
package main

func isBipartite(graph [][]int) bool {
    n := len(graph)
    color := make([]int, n) // 0 = unvisited, 1 / -1 = two classes
    for start := 0; start < n; start++ {
        if color[start] != 0 {
            continue
        }
        color[start] = 1
        q := []int{start} // small slice queue; OK at LC 785 cap n <= 100
        for len(q) > 0 {
            u := q[0]
            q = q[1:] // O(1) amortized via underlying-array offset
            for _, v := range graph[u] {
                if color[v] == 0 {
                    color[v] = -color[u]
                    q = append(q, v)
                } else if color[v] == color[u] {
                    return false
                }
            }
        }
    }
    return true
}

Three things in the body deserve attention.

The colors are 1 and -1, not 0 and 1. That choice lets color[v] = -color[u] flip the color in one operation; using 0 and 1 would force a 1 - color[u] or a XOR with 1, both of which read fine but make the “paint the opposite” intent slightly less direct. The third value, 0, means “unvisited”, and the test color[v] == 0 gates BFS entry to vertices we haven’t touched yet.

The decision at each edge is exactly three-way. The neighbor v is uncolored, in which case paint it the opposite of u and enqueue. Or v is already colored the opposite of u, in which case the edge is consistent and we move on. Or v is already colored the same as u, which is the only way the algorithm returns false.

flowchart TD
    Start([Edge u-v examined during BFS]) --> Cmp{color of v?}
    Cmp -->|uncolored| Paint[v := opposite of u; enqueue v]
    Cmp -->|same as u| Reject[return false: odd cycle witnessed]
    Cmp -->|opposite of u| Skip[continue: edge consistent]
    Paint --> Done
    Skip --> Done
    Done([next edge])

The outer for start in range(n) loop is doing more work than it looks. LC 785’s problem statement explicitly says “the graph may not be connected.” If you BFS only from vertex 0 and stop, you’ll miss components 1, 2, 3, … and can falsely return True on a graph whose unvisited components contain odd cycles. The cost of the outer loop on a connected graph is zero (every later iteration trips the continue immediately), so there is no reason not to write it.²

Worked example: LC 785 on a 4-cycle and on a triangle

Take Example 2 from LC 785: graph = [[1,3],[0,2],[1,3],[0,2]]. That’s the four-cycle 0-1-2-3-0 from the opening.

flowchart LR
    A((0 / red)) --- B((1 / blue))
    A --- D((3 / blue))
    B --- C((2 / red))
    C --- D

Start at vertex 0. Color 0 red, push to queue. Pop 0, walk its neighbors: 1 is uncolored, so color it blue and push; 3 is uncolored, color blue, push. Pop 1, walk its neighbors: 0 is already red (opposite of 1, consistent); 2 is uncolored, color red, push. Pop 3, walk neighbors: 0 red (opposite, consistent); 2 red (opposite, consistent). Pop 2, walk neighbors: 1 blue, 3 blue, both consistent. Queue empty, no conflict. Return True.

Now take Example 1: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]. There’s a triangle hiding inside (vertices 0-1-2-0).

flowchart LR
    X0((0)) --- X1((1))
    X0 --- X2((2))
    X0 --- X3((3))
    X1 --- X2
    X2 --- X3

Start at vertex 0. Color 0 red, push. Pop 0, walk neighbors: 1 uncolored, color blue, push; 2 uncolored, color blue, push; 3 uncolored, color blue, push. Pop 1, walk neighbors: 0 red (opposite, fine); 2 blue, same as 1. Return False. The triangle’s third edge fired the same-color check, exactly as König’s theorem predicts.

What it actually costs

The amortization argument is short. Every vertex is enqueued exactly once across all BFS runs (the color[v] == 0 test gates the assignment). Every edge is examined twice, once from each endpoint in the undirected adjacency-list representation, and the per-edge work is one O(1) color comparison.³ The outer loop over disconnected components adds at most O(V) extra iterations across all components combined. Total: O(V) + O(2E) · O(1) = O(V + E). The bound is tight: a path on V vertices with V - 1 edges takes Θ(V + E) to certify bipartite, since every edge has to be checked.

When the pattern bends

The two-color case is the special one. Its variants either swap BFS for DFS, change the input shape, or push past two colors entirely.

DFS as an alternative

BFS and DFS both implement the same proof: an odd cycle exists if and only if 2-coloring fails. DFS uses recursion or an explicit stack; the body becomes “for each neighbor, recurse with the opposite color or check the existing color matches.” The two algorithms produce different cycle witnesses when one is found. DFS’s witness is the path on the recursion stack from u back to v, which interviewers sometimes ask for as a follow-up. The linear-time bound is the same.⁴ Pick BFS by default in Python: the recursion limit (1000 by default) blows on adversarially deep chains, and sys.setrecursionlimit is a workaround you’d rather not need.

Edge-list input, 1-indexed

LC 886 Possible Bipartition takes dislikes = [[1,2],[1,3],[2,4]] and asks whether n people can be split into two groups so no disliked pair shares a group. The algorithm is unchanged once you build adjacency from the edge list. The trap is the 1-indexed input: people are numbered 1 to n, so color = [0] * n indexed at color[n] is out of bounds. Either size the array n + 1 and ignore index 0 (cleaner), or convert to 0-indexed at ingest. Pick one; mixing them is how silent wrong-answers happen.⁵

K-coloring with k ≥ 3

The bipartite-check intuition does not extend. 3-coloring (and any k ≥ 3 chromatic-number decision) is NP-complete in general; it’s one of Karp’s 21 original problems. LC 1042 Flower Planting With No Adjacent asks for 4-coloring on a graph with max degree 3, and looks at first like a generalization of bipartite check. It isn’t. The problem is solvable in linear time for a different reason: with max degree 3, every vertex has at most three neighbors, so at least one of four colors is always unused on the neighborhood. A greedy single pass picks any unused color and moves on. The “guaranteed answer exists” line in the problem statement is a pre-cooked instance of Brooks’ theorem (chromatic number ≤ Δ for non-complete-non-odd-cycle graphs).⁶

The lesson buried inside LC 1042 is the boundary. Bipartite check (Δ ≥ 1, k = 2) and degree-bounded greedy coloring (k > Δ) are both linear. Everything in between, graph k-coloring without degree bounds, is NP-complete. An odd cycle of any length needs three colors despite Δ = 2, which is the exact case Brooks’ theorem carves out and the reason 2-coloring is special.

Two pitfalls that bite

A third trap worth naming: conflating bipartite check with bipartite matching. They share a name and a graph type and almost nothing else. Bipartite check decides whether a 2-partition exists. Bipartite matching, given that one does, finds the largest set of edges with no shared endpoint. The matching problem is solved by Hopcroft-Karp or by max-flow, lives in a future chapter, and is not what an interviewer means when they hand you LC 785.

Problem ladder

CORE (solve all three to claim chapter mastery)

• LC 785: Is Graph Bipartite? [Medium] • bipartite-check ★
• LC 886: Possible Bipartition [Medium] • bipartite-check
• LC 1042: Flower Planting With No Adjacent [Easy] • graph-coloring

STRETCH (optional)

• LC 684: Redundant Connection [Medium] • cycle-detection (free mirror of the Premium Graph Valid Tree)

LC 785 is the chapter’s signature problem (★) and the one the worked example walks through. LC 886 is the same algorithm under a different name; the build-the-graph step and the 1-indexed handling are the only new work. LC 1042 is the Easy slot through the adjacent-pattern door: not 2-coloring, but the same paint-and-traverse skeleton, and a useful boundary marker for where the technique stops applying.

There is no canonical Hard for this chapter, and that’s an honest gap, not a curation choice. The natural Hard variants of bipartite-check drift into bipartite matching (König via max-flow, future chapter), odd cycle transversal (NP-complete), or edge bipartization (NP-complete). LC’s Hard graph problems that touch this territory teach genuinely different algorithms.

Where this leads

Cycle detection is the dual: bipartite check IS odd-cycle detection, dressed in different vocabulary, and the chapter on cycles formalizes the relationship. Union-Find supports the online variant where edges arrive one at a time and you report bipartiteness after each insertion; the technique is “Union-Find with parity,” a parent-edge bit that tracks whether the path from a node to its representative is even or odd in length. The matching problem (find the largest set of edges with no shared endpoint, given that the graph is bipartite) waits for the network-flow chapter.

References