p67 — Is Graph Bipartite?

Source: LeetCode 785 · Medium · Topics: Graph, BFS, DFS, 2-coloring Companies (2024–2025): Meta (high), Google (medium-high), Amazon (medium), Microsoft (medium) Loop position: Bipartite check canonical. Equivalent to “graph has no odd cycle.” Tests 2-coloring via BFS/DFS — a clean, named, provable algorithm that’s the gateway to matching theory.

1. Quick Context

Undirected graph as adjacency list graph[i]. Return True if you can partition the nodes into two sets A and B such that every edge goes between A and B.

Theorem (König 1936): A graph is bipartite ⟺ it contains no odd-length cycle.

Algorithm: 2-color via BFS. Color start node 0; alternate colors across edges. Conflict → not bipartite.

color = [-1] * n
for start in range(n):
    if color[start] != -1: continue
    color[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if color[v] == -1:
                color[v] = 1 - color[u]
                q.append(v)
            elif color[v] == color[u]:
                return False
return True

O(V + E). Iterate over all start nodes to handle disconnected components.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/is-graph-bipartite/

STOP. 20-min timer.

3. Prerequisite Concepts

  • BFS / DFS traversal of an undirected graph.
  • Disconnected components (must restart traversal from each unvisited node).
  • The 2-coloring invariant: each edge has endpoints of different colors.
  • (Background) König’s theorem: bipartite ⟺ no odd cycle.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Partition nodes into two sets so that every edge crosses the partition. Equivalent: 2-color the graph.

2. Clarify: Self-loops? (A self-loop is a length-1 cycle = odd cycle → not bipartite. LC’s graph has none typically.) Multi-edges? Don’t change bipartiteness.

3. Examples: graph = [[1,3],[0,2],[1,3],[0,2]] (4-cycle) → True. graph = [[1,2,3],[0,2],[0,1,3],[0,2]] (has triangle 0-1-2) → False.

5. Brute force: Try all 2^n colorings; verify each. Exponential.

6. Target: O(V + E).

7. Pattern: BFS/DFS + 2-coloring.

8. Develop: see solution.py.

9. Test: disconnected components (each must be independently bipartite); single node (True); single edge (True); triangle (False); odd cycle of length 5 (False); even cycle (True).

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 König’s theorem — the why

Bipartite ⟺ no odd cycle.

(⇒) If graph is bipartite with parts A, B, any cycle alternates A-B-A-B-… and must have even length to return to start.

(⇐) Suppose no odd cycle. BFS from any vertex; color by BFS-depth parity. Claim: this is a valid 2-coloring. If an edge (u, v) has same-color endpoints, then depth(u) ≡ depth(v) (mod 2), but |depth(u) − depth(v)| ≤ 1 (BFS tree edge) so depth(u) = depth(v). The path u→LCA→v in the BFS tree plus edge (u,v) is an odd cycle — contradiction.

This is why BFS-by-depth-parity works as the coloring rule.

6.2 DFS variant

DFS works just as well: color each node opposite to its parent. Conflict on a back-edge with same color → not bipartite.

def dfs(u, c):
    color[u] = c
    for v in graph[u]:
        if color[v] == -1:
            if not dfs(v, 1 - c): return False
        elif color[v] == c:
            return False
    return True

Recursive risks stack overflow on long chains (n up to 10⁴ on LC is borderline). Iterative DFS with explicit stack is safer.

6.3 Disconnected components

Critical: iterate over ALL starting nodes (for start in range(n)), not just one. A disconnected graph is bipartite ⟺ EVERY component is bipartite.

Common bug: starting BFS only from node 0 — silently passes connected tests, fails on disconnected ones.

6.4 Connection to matching theory

Bipartite graphs admit polynomial-time maximum matching (König’s theorem: max matching = min vertex cover, both polynomial via augmenting paths / Hopcroft-Karp O(E√V)). Non-bipartite max matching is harder (Blossom algorithm, Edmonds 1965, O(V³)). The “is bipartite” check is the gatekeeper for which matching algorithm to deploy.

6.5 Union-Find variant

You can also detect bipartiteness via DSU with a parity-weighted version:

  • For each edge (u, v): union(u, v) with weight 1 (different colors).
  • If u and v are already in the same component, check that the parity-distance from u to root XOR distance from v to root = 1.

More complex than BFS for this problem but generalizes to constraint-satisfaction graphs (e.g., “u and v differ by k mod m”).

6.6 Why “is bipartite” is a fundamental check

Many problems implicitly assume bipartiteness:

  • Stable matching (Gale-Shapley) requires bipartite.
  • Maximum flow problems on bipartite networks reduce to matching.
  • Graph coloring with 2 colors = bipartite check.

Knowing the check costs O(V + E) tells you when the cheap algorithm suffices.

6.7 LC 886 Possible Bipartition

Same problem, dressed up: “Given dislike pairs, can you split into two groups so no two who dislike each other are together?” Build graph from pairs; run bipartite check.

LC 785 (this one) gives you the graph; LC 886 makes you build it. Solution is identical.

7. Anti-Pattern Analysis

  1. Start BFS only from node 0 — fails on disconnected components.
  2. Color with 0/1 and use truthy check if color[v] — node 0 colored 0 evaluates falsy; bug. Use -1 as uncolored sentinel.
  3. Recursive DFS without depth-limit awareness on huge chains — stack overflow.
  4. Try set instead of [-1]*n — slower; lookups become hashable-key overhead.
  5. Skip the second check (elif color[v] == color[u]) — silent True on non-bipartite graphs.
  6. Bipartite via 2^n brute force — would technically work but trivially blows up; not a serious option.

8. Skills & Takeaways

  • 2-coloring as a BFS/DFS invariant.
  • König’s theorem and the odd-cycle characterization.
  • Disconnected-component handling: iterate over all starts.
  • Recognize bipartite check as a gatekeeper for matching / coloring problems.

9. When to Move On

  • Solve LC 785 cold in 12 min with BFS.
  • Solve LC 886 cold in 15 min (with graph construction).
  • State König’s theorem and sketch the proof in 60 seconds.
  • Convert your BFS to iterative DFS.

10. Company Context

  • Meta: E5; appears as a sub-problem in social-graph community detection / dislike-grouping.
  • Google: L5; ad-placement bipartite matching prep.
  • Amazon: L5; order-fulfillment bipartite assignment.

Scorecard for strong: “BFS 2-color over all components, used -1 sentinel, cited König’s theorem, mentioned matching applications.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
AlgorithmVagueBFS, single component+ all components, clean+ DFS variant + DSU with parity
ProofNone“alternate colors”König’s theorem stated+ sketches proof + connects to matching
Edge casesMisses disconnectedCatches with promptHandles cleanly+ self-loop + multi-edge analyzed
ApplicationsNone“graph coloring”+ matching theory+ LP relaxation + Hopcroft-Karp + Blossom

12. Level Delta

  • Mid (L4): BFS 2-color, handles disconnected components, returns correct answer.
  • Senior (L5): + DFS variant + König’s theorem + LC 886 reduction.
  • Staff (L6): + DSU with parity for general constraint graphs + connection to bipartite matching (Hopcroft-Karp O(E√V)) + Blossom for non-bipartite.
  • Principal (L7+): + matroid generalization + LP relaxation + production matching systems (ride-hailing, ad-auction).

13. Follow-up Q&A

Q1: Now find the two parts explicitly. A1: Return color array. Nodes with color 0 = part A, color 1 = part B.

Q2: What if the graph might be directed? A2: Bipartiteness is an undirected concept. For directed, ignore directions (treat as undirected) and run the same check.

Q3: What if you must split into THREE groups (3-coloring)? A3: 3-coloring is NP-complete (vs polynomial for 2). Use backtracking + pruning, or heuristics.

Q4: Now ALSO find the maximum matching in the bipartite graph. A4: Hopcroft-Karp O(E√V); or Hungarian algorithm for weighted bipartite matching.

Q5: What if edges are weighted with “this edge prefers same-side” weights? A5: That’s the MAX-CUT problem (find a cut maximizing crossing-edge weight). NP-hard in general; 0.878-approx via Goemans-Williamson SDP. Vastly harder than 2-coloring.

14. Solution Walkthrough

See solution.py:

  • is_bipartite_bfs — BFS 2-coloring (canonical).
  • is_bipartite_dfs — iterative DFS 2-coloring.
  • is_bipartite_brute — try all 2^n colorings (n ≤ 8 for stress only).

15. Beyond the Problem

Principal code review: “Bipartite check is one of those algorithms that looks trivial but anchors an entire theory. König’s theorem connects bipartiteness, matching, vertex cover, and LP duality — four notions that turn out to be the same on bipartite graphs and meaningfully different elsewhere. The 30-line BFS you wrote tells you whether you can deploy Hopcroft-Karp’s O(E√V) matching or have to escalate to Edmonds’ O(V³) Blossom. In production systems — ride-hailing matching, ad-auction allocation, kidney-exchange chains — that O(V³) vs O(E√V) choice is the difference between real-time and batch. Memorize the BFS; learn the theorem; respect the consequences.”