Bipartite Check
A graph is bipartite if its vertex set can be partitioned into two disjoint groups
UandVsuch that every edge connects a vertex inUto a vertex inV— i.e., no edge stays within a group. The classical theorem (König, 1936) is that a graph is bipartite iff it contains no cycle of odd length. Equivalently, a graph is bipartite iff it can be 2-colored: assign each vertex one of two colors such that adjacent vertices have different colors. Both BFS and DFS check bipartiteness inO(V + E)by attempting a 2-coloring layer by layer (BFS) or branch by branch (DFS); a same-color edge collision proves non-bipartiteness. Bipartite checking is the gateway to maximum bipartite matching (Hopcroft-Karp, Hungarian algorithm), scheduling under conflicts, and many constraint-satisfaction problems.
1. Intuition — Two Teams at a Party
Imagine a party where some pairs of attendees know each other (drawn as graph edges). You want to split everyone into two teams — call them Team Red and Team Blue — such that every pair who knows each other ends up on opposite teams. (Maybe the party is a debate tournament; you don’t want acquaintances on the same side.)
When can you do it? The trick is consistency:
- Pick anyone, put them on Red.
- Their acquaintances must all go on Blue.
- Their acquaintances (one more hop out) must all go back on Red.
- And so on, alternating with every step.
This works fine until you encounter a contradiction: a vertex that, by one path, “should” be Red, and by another path, “should” be Blue. That contradiction can only arise from a cycle of odd length — because an odd cycle forces the start and end (which are the same vertex!) to be opposite colors, which is impossible.
If you make it through the entire graph with no contradictions, the assignment witnesses bipartiteness. If a contradiction appears, the graph contains an odd cycle and is not bipartite.
That’s the entire algorithm: do a graph traversal (BFS or DFS), color as you go, fail loudly on a same-color edge.
2. Tiny Worked Example
2.1 A Bipartite Graph
Vertices 0..5, edges {(0,1), (0,3), (1,2), (1,4), (2,5), (3,4)}.
0 — 1 — 2
| | |
3 — 4 5
Try BFS from 0, color it Red:
| Step | Queue | Just colored | New colors |
|---|---|---|---|
| 1 | [0] | 0 → Red | |
| 2 | dequeue 0 → enqueue 1 (Blue), 3 (Blue) | 1=Blue, 3=Blue | |
| 3 | dequeue 1 → enqueue 2 (Red), 4 (Red); 0 already Red, OK | 2=Red, 4=Red | |
| 4 | dequeue 3 → enqueue (none); 0 Red OK, 4 Red OK | ||
| 5 | dequeue 2 → enqueue 5 (Blue); 1 Blue OK | 5=Blue | |
| 6 | dequeue 4 → 1 Blue OK, 3 Blue OK | ||
| 7 | dequeue 5 → 2 Red OK |
Final coloring: {0:R, 1:B, 2:R, 3:B, 4:R, 5:B}. Sets: U = {0, 2, 4}, V = {1, 3, 5}. Every edge crosses; the graph is bipartite.
2.2 A Non-Bipartite Graph
Add edge (0, 2) to the graph above. Now 0 — 1 — 2 — 0 is a triangle (odd cycle).
BFS from 0: 0=Red. Enqueue 1=Blue, 3=Blue. Dequeue 1: enqueue 2=Red, 4=Red. Dequeue 3: enqueue (none new). Dequeue 2: examine neighbor 0 — 0 is Red, but 2 is Red. Same-color collision → not bipartite.
The triangle 0-1-2-0 has length 3 (odd), confirming König’s theorem.
3. Pseudocode (BFS-Based)
is_bipartite(graph): # graph: undirected adjacency list
color := array, all -1 # -1 = uncolored
for each s in V:
if color[s] == -1: # new connected component
color[s] := 0
queue := [s]
while queue not empty:
u := dequeue
for each v in graph[u]:
if color[v] == -1:
color[v] := 1 - color[u] # opposite color
enqueue v
else if color[v] == color[u]:
return false # same-color edge ⇒ odd cycle
return true
4. Python Implementation (BFS)
from collections import deque
def is_bipartite_bfs(graph: dict[int, list[int]], n: int) -> bool:
"""
graph: undirected adjacency list (each edge appears in both endpoints' lists).
n: number of vertices, 0..n-1.
Returns True iff the graph is bipartite.
"""
color = [-1] * n
for s in range(n):
if color[s] != -1:
continue
color[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in graph.get(u, []):
if color[v] == -1:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return False
return True5. Python Implementation (DFS — Recursive)
import sys
def is_bipartite_dfs(graph: dict[int, list[int]], n: int) -> bool:
sys.setrecursionlimit(max(10**6, n + 100))
color = [-1] * n
def dfs(u: int, c: int) -> bool:
color[u] = c
for v in graph.get(u, []):
if color[v] == -1:
if not dfs(v, 1 - c):
return False
elif color[v] == c:
return False
return True
for s in range(n):
if color[s] == -1:
if not dfs(s, 0):
return False
return TrueBoth return identical results on identical inputs; the difference is traversal order, not correctness. BFS is preferable when the graph might be deep (avoids recursion-depth issues); DFS is shorter to write.
6. Why It Works — Proof Sketch
Claim. The BFS/DFS 2-coloring algorithm reports “bipartite” iff the graph has no odd cycle (König’s theorem direction we need).
(⇐) If no odd cycle, algorithm succeeds. Since the graph has no odd cycle, every cycle has even length. We claim BFS produces a consistent 2-coloring: assign color = parity of BFS distance from the source. Take any edge (u, v). If u and v are at the same BFS distance d from the source s, then s ⇝ u and s ⇝ v are paths of length d, and combined with edge (u, v) they form a closed walk of length 2d + 1 (odd). Within such a walk, an odd cycle must exist (graph theory: an odd closed walk contains an odd cycle as a subgraph). Contradiction with “no odd cycle.” So adjacent vertices have different BFS-distance parities; the parity coloring is a valid 2-coloring.
(⇒) If algorithm succeeds, no odd cycle. A 2-coloring forbids any cycle of odd length (in a cycle, alternating colors must end at the start, requiring even length). Trivial.
So the algorithm’s two outcomes correspond exactly to the two possibilities König’s theorem identifies. The algorithm is a constructive certificate either way: success returns a 2-coloring; failure returns a same-color edge that closes an odd cycle.
7. Complexity
- Time:
O(V + E). Each vertex is enqueued/dequeued (or recursed into) once; each edge is examined at most twice (once from each endpoint). - Space:
O(V)for the color array + queue (BFS) or recursion stack (DFS).
This is asymptotically tight: certifying bipartiteness requires examining every edge to verify it’s bichromatic.
8. Variants
8.1 Returning the 2-Partition (Not Just Yes/No)
Easy modification: after a successful coloring, return (set_of_color_0, set_of_color_1) instead of True. The same algorithm; just expose the color array.
8.2 Returning a Witness Odd Cycle
When a same-color collision occurs at edge (u, v), the cycle is found by tracing back through BFS parents from both u and v until they meet at a common ancestor. Length: dist[u] + dist[v] + 1. The cycle is odd (since dist[u] == dist[v]). Useful for problems that need an explicit “this is why your graph isn’t bipartite” certificate.
8.3 Bipartite Check on Disconnected Graphs
Run the algorithm independently on each connected component. The graph is bipartite iff every component is. A disconnected graph can be bipartite even if some components have odd cycles? No — a single odd cycle anywhere makes the whole graph non-bipartite, because bipartiteness is a global property. The outer for s in range(n) loop handles this correctly.
8.4 Online Bipartite Check (with Edge Insertions)
If you want to maintain bipartiteness while adding edges, use a Union-Find structure with rank/parity offsets: each find(u) returns not just a root but also the parity of the path from u to the root. To add edge (u, v), check whether u and v are in the same component; if so, verify their parities differ. This supports online bipartite check in O(α(n)) amortized per edge insertion, beating recomputation. Edge deletion remains hard.
8.5 Multi-Coloring (k-Coloring) Generalization
Bipartite is the k=2 case of Graph Coloring. For k=3 and above, the problem becomes NP-hard (Karp 1972) — there’s no known polynomial algorithm for k-colorability with k ≥ 3. The jump from k=2 (linear time) to k=3 (NP-complete) is one of the sharpest complexity transitions in graph algorithms.
9. Use Cases and Why It’s Important
9.1 Bipartite Matching
Matching algorithms (e.g., Hopcroft-Karp, Hungarian algorithm) are designed for bipartite graphs. Before running matching, you check bipartiteness. Job-assignment problems, marriage problems, and resource-allocation problems are typically modeled as bipartite matching.
9.2 Conflict Scheduling
If you model “conflicts” as edges (two tasks that can’t run at the same time), bipartiteness asks “can these tasks be split into 2 timeslots?” An odd cycle of conflicts means 2 timeslots aren’t enough. Generalizes to chromatic number for k slots.
9.3 Constraint Satisfaction
Many CSPs reduce to “color this graph with 2 colors”: e.g., assigning ±1 spins in physics, T/F to literals such that conflicting pairs differ. Bipartiteness is a necessary feasibility check.
9.4 Two-Sided Matching Markets
Stable-marriage and labor-market matching all start by establishing the bipartite structure (workers vs jobs). The check is trivial when the bipartition is known by construction; non-trivial when given a graph and asked whether such a partition exists.
9.5 Detecting “Tree Plus a Few Edges” Structures
Trees are always bipartite (no cycles ⇒ no odd cycles). A graph that’s “a tree plus one extra edge” is bipartite iff the extra edge creates an even-length cycle. This trivia comes up in graph-classification interview questions.
9.6 Hall’s Theorem and Marriage Conditions
Once a graph is verified bipartite, Hall’s theorem gives a characterization of when a perfect matching exists: every subset S ⊆ U has |N(S)| ≥ |S|. The bipartite check is the precondition for asking these deeper questions.
9.7 Bipartite vs Tripartite Detection
Some problems ask “is this graph 3-partite?” — partitionable into 3 independent sets. This is NP-hard in general (it’s literally 3-coloring). The 2-partition case (bipartite) is the only polynomial-time member of the family, which is why interview questions stop at bipartite.
10. Common Interview Problems
| Problem | Pattern |
|---|---|
| LC 785 — Is Graph Bipartite? | Direct application of BFS/DFS 2-coloring |
| LC 886 — Possible Bipartition | Same as 785, with input as conflict edges |
| LC 1042 — Flower Planting With No Adjacent | k=4 coloring (always solvable for max-degree-3) — bipartiteness reasoning extends |
| Classic — “Detect odd cycle in undirected graph” | Equivalent to bipartite check |
| Classic — Maximum bipartite matching | Bipartite check is the first step |
| LC 765 — Couples Holding Hands | Union-Find variant; bipartite check is a related framing |
| Classic — “2-color a graph or report odd cycle” | This algorithm with witness extraction (§8.2) |
| Codeforces — “Equivalence-class scheduling under exclusions” | Bipartite check / 2-SAT encoding |
If a problem mentions “two groups”, “divide into red and blue”, “opposite teams”, “alternating coloring”, or “odd cycle” — bipartite check is on the shortlist.
11. Diagram — BFS Layering and the 2-Coloring
flowchart TD S((s<br/>color=0<br/>distance=0)) --- A((A<br/>color=1<br/>distance=1)) S --- B((B<br/>color=1<br/>distance=1)) A --- C((C<br/>color=0<br/>distance=2)) A --- D((D<br/>color=0<br/>distance=2)) B --- D C --- E((E<br/>color=1<br/>distance=3))
What this diagram shows. Starting BFS from source s (color 0, distance 0), every neighbor (A, B) gets distance 1 and color 1. Their neighbors (C, D) get distance 2 and color 0. The pattern is parity of BFS distance = color. Edge (A, D) and edge (B, D) are both between distance-1 and distance-2 vertices — different colors, OK. Edge (C, E) is between distance-2 and distance-3, different colors, OK. If there were an edge between A and B (both distance 1, both color 1), we’d have a same-color collision and the algorithm would report “not bipartite.” Such an edge would close an odd-length cycle s → A → B → s of length 3.
12. Pitfalls
12.1 Forgetting to Iterate Over Disconnected Components
If you only run BFS from vertex 0, you miss every vertex unreachable from 0. Bipartiteness is a global property: any connected component with an odd cycle makes the whole graph non-bipartite. The outer for s in range(n): if color[s] == -1 loop is essential.
12.2 Using a Boolean Visited Array Instead of a Tri-State Color Array
Tempting to write if visited[v]: ... — but you’ve lost the color information needed to detect collisions. Use color[v] in {-1, 0, 1} as both the visited marker and the color. The -1 sentinel doubles as “unvisited.”
12.3 Self-Loops Always Break Bipartiteness
A vertex v with edge (v, v) cannot be 2-colored: v must be a different color from itself, impossible. The algorithm’s color[v] == color[u] check correctly returns False on a self-loop (same vertex, same color, edge between them). Just make sure you don’t skip self-loops in your adjacency-list iteration.
12.4 Treating the Graph as Directed
Bipartite check is for undirected graphs. If your input is directed, convert it to undirected first (replace each directed edge (u, v) with an undirected edge between u and v). Running the algorithm on a directed graph (interpreting edges as directed) gives meaningless results.
12.5 Edge Weights Don’t Matter
Bipartiteness is purely topological; edge weights are irrelevant. Don’t try to incorporate them into the coloring decision. (Some problems mash “bipartite” with “minimum-weight” — those are bipartite matching problems, not bipartite check.)
12.6 Large Sparse Graphs and Recursion Depth
DFS-based bipartite check on a graph with a 10^5-long path overflows Python’s default recursion limit. Either use the BFS version or sys.setrecursionlimit(N) (with N safely above the longest path).
12.7 Multigraphs (Parallel Edges)
Parallel edges between u and v don’t change bipartiteness — u and v must still have different colors. The algorithm handles parallel edges correctly without modification (it just re-checks the same edge multiple times harmlessly).
12.8 Vertices With No Edges
A vertex with degree 0 is trivially “bipartite-compatible” — it can be put in either group. The outer loop colors it with color 0 (arbitrary). Not a bug; just a reminder that isolated vertices are fine.
12.9 The Phrase “Equivalent To Tree Plus Even-Length Path”
A common misconception: “bipartite means tree-like.” False. Complete bipartite graphs K_{m,n} are dense (have m·n edges) and bipartite. Bipartite ≠ sparse; bipartite = no odd cycles.
13. Open Questions
- How efficiently can we maintain bipartite check under both insertions and deletions? Holm-Lichtenberg-Thorup-style data structures achieve
O(log² n)amortized; recent work improves this. Verify state of the art. - Is there a randomized algorithm faster than
O(V + E)for bipartite check? Probably not — you must look at every edge — but lower bounds for sublinear algorithms (with property-testing relaxation) exist.
14. See Also
- Breadth-First Search — natural traversal for layered 2-coloring
- Depth-First Search — alternative traversal; recursive form is shorter
- Connected Components — bipartite check runs per component
- Union-Find — supports online bipartite check with parity offsets
- Graph Coloring — bipartite is the k=2 special case
- Strongly Connected Components — analogous “decompose by structure” idea for directed graphs
- Big-O Notation
- SWE Interview Preparation MOC