Bipartite Graph Check: BFS 2-Coloring and DFS Approaches

A bipartite graph is one where you can split all vertices into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. No edge connects two vertices within the same set. This property appears everywhere: matching students to projects, scheduling exams (no two conflicting exams at the same time), and determining if a social network has two distinct groups.

The key insight is simple: a graph is bipartite if and only if it contains no odd-length cycle. This gives us an efficient algorithm based on 2-coloring.

The 2-Coloring Idea

Think of it like painting vertices with two colors (say, red and blue). Start from any vertex and color it red. Color all its neighbors blue. Color all their uncolored neighbors red. If you ever need to color a vertex that already has the same color as its neighbor, the graph is not bipartite.

This is exactly what BFS does level by level. Vertices at even levels get one color, vertices at odd levels get the other.

BFS 2-Coloring Algorithm

from collections import deque

def is_bipartite_bfs(graph: dict[int, list[int]]) -> bool:
    """
    Check if an undirected graph is bipartite using BFS 2-coloring.
    graph: adjacency list {node: [neighbors]}
    Returns True if graph is bipartite.
    """
    color = {}  # node -> 0 or 1
    
    # Handle disconnected components
    for start in graph:
        if start in color:
            continue
        
        # BFS from this unvisited node
        queue = deque([start])
        color[start] = 0
        
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    # Color with opposite color
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    # Same color as neighbor = not bipartite
                    return False
    
    return True

Step-by-Step Walkthrough

Consider this graph: 0-1, 1-2, 2-3, 3-0 (a 4-cycle, which is bipartite).

1. Start BFS from node 0, color it 0 (red)
2. Visit neighbor 1: uncolored, color it 1 (blue)
3. Visit neighbor 3: uncolored, color it 1 (blue)
4. Process node 1: neighbor 0 has color 0, node 1 has color 1, OK. Neighbor 2: uncolored, color it 0 (red)
5. Process node 3: neighbor 0 has color 0, node 3 has color 1, OK. Neighbor 2 has color 0, node 3 has color 1, OK
6. Process node 2: neighbor 1 has color 1, node 2 has color 0, OK. Neighbor 3 has color 1, node 2 has color 0, OK

No conflicts found. The graph is bipartite with sets {0, 2} and {1, 3}.

Now consider a triangle: 0-1, 1-2, 2-0 (a 3-cycle, odd length).

1. Color node 0 with 0
2. Color node 1 with 1
3. Color node 2 with 0 (neighbor of node 1)
4. Check edge 2-0: both have color 0. Conflict! Not bipartite.

DFS 2-Coloring Algorithm

The same logic works with DFS. Instead of level-by-level exploration, we go deep and color as we recurse.

def is_bipartite_dfs(graph: dict[int, list[int]]) -> bool:
    """
    Check if an undirected graph is bipartite using DFS 2-coloring.
    """
    color = {}
    
    def dfs(node: int, c: int) -> bool:
        color[node] = c
        for neighbor in graph[node]:
            if neighbor not in color:
                if not dfs(neighbor, 1 - c):
                    return False
            elif color[neighbor] == c:
                return False
        return True
    
    for node in graph:
        if node not in color:
            if not dfs(node, 0):
                return False
    
    return True

Iterative DFS Version

For large graphs, recursion may hit Python’s stack limit. Here is an iterative version.

def is_bipartite_dfs_iterative(graph: dict[int, list[int]]) -> bool:
    """Iterative DFS to avoid recursion depth issues."""
    color = {}
    
    for start in graph:
        if start in color:
            continue
        
        stack = [start]
        color[start] = 0
        
        while stack:
            node = stack.pop()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]
                    stack.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    
    return True

LeetCode 785: Is Graph Bipartite?

The classic problem gives you an adjacency list directly.

def isBipartite(graph: list[list[int]]) -> bool:
    """
    LeetCode 785: graph[i] is list of neighbors of node i.
    """
    n = len(graph)
    color = [-1] * n
    
    for i in range(n):
        if color[i] != -1:
            continue
        
        queue = deque([i])
        color[i] = 0
        
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append(nei)
                elif color[nei] == color[node]:
                    return False
    
    return True

Possible Bipartition (LeetCode 886)

A more applied version: given N people and a list of mutual dislikes, can you split them into two groups so nobody in the same group dislikes each other?

This is exactly bipartite checking. People are nodes, dislikes are edges.

def possibleBipartition(n: int, dislikes: list[list[int]]) -> bool:
    """
    LeetCode 886: Can we split n people into two groups
    so no two people in the same group dislike each other?
    """
    # Build adjacency list
    graph = [[] for _ in range(n + 1)]
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)
    
    color = [-1] * (n + 1)
    
    for i in range(1, n + 1):
        if color[i] != -1:
            continue
        
        queue = deque([i])
        color[i] = 0
        
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append(nei)
                elif color[nei] == color[node]:
                    return False
    
    return True

Why Odd Cycles Break Bipartiteness

The mathematical proof is clean. In a bipartite graph with sets A and B, every edge crosses from A to B or B to A. Walking along a path, you alternate sets: A, B, A, B, A, … To return to your starting set, you need an even number of steps. An odd cycle means you return to the starting vertex after an odd number of steps, which means you need it to be in both sets simultaneously. Contradiction.

In terms of 2-coloring: walking along an odd cycle, you flip the color at each step. After an odd number of flips, you return to the opposite color. But you are back at the same vertex, which cannot have two colors.

Union-Find Approach

There is a less common but elegant approach using Union-Find. For each node, all its neighbors must be in the opposite set. So we union all neighbors together (they should all be in the same set).

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1


def is_bipartite_uf(graph: list[list[int]]) -> bool:
    """
    Union-Find approach: for each node, union all its neighbors.
    If node ends up in the same set as any neighbor, not bipartite.
    """
    n = len(graph)
    uf = UnionFind(n)
    
    for node in range(n):
        for nei in graph[node]:
            # node and nei should be in different sets
            # So all neighbors of node should be in the same set
            if uf.find(node) == uf.find(nei):
                return False
            # Union nei with the first neighbor of node
            uf.union(graph[node][0], nei)
    
    return True

The idea: for each node, we union all its neighbors into one group. If the node itself ends up in that group, we have a conflict.

Applications of Bipartite Graphs

Job Assignment / Matching

In bipartite matching, one set is workers and the other is jobs. Edges represent which workers can do which jobs. Finding a maximum matching (assigning the most workers to jobs) is a classic problem solved by the Hungarian algorithm or Hopcroft-Karp.

Exam Scheduling

Students and exams form a bipartite relationship. Two exams conflict if a student takes both. The chromatic number of the conflict graph tells you the minimum number of time slots needed. If the conflict graph is bipartite, you need only 2 time slots.

Two-Colorable Maps

Can you color a map with 2 colors so no two adjacent regions share a color? This is exactly bipartite checking on the adjacency graph of regions.

Edge Cases and Gotchas

1. Disconnected graphs: You must check every component. A graph is bipartite only if ALL components are bipartite.

2. Self-loops: A self-loop means a node is adjacent to itself. It needs two colors simultaneously, which is impossible. Any graph with a self-loop is not bipartite.

3. Single node: A graph with one node and no edges is bipartite (trivially).

4. Empty graph: A graph with no edges is bipartite. Every node can go in either set.

def is_bipartite_with_edge_cases(graph: list[list[int]]) -> bool:
    """Handle edge cases explicitly."""
    n = len(graph)
    if n == 0:
        return True
    
    # Check for self-loops
    for i in range(n):
        if i in graph[i]:
            return False
    
    color = [-1] * n
    for i in range(n):
        if color[i] != -1:
            continue
        queue = deque([i])
        color[i] = 0
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append(nei)
                elif color[nei] == color[node]:
                    return False
    return True

Complexity Analysis

Approach	Time	Space	Notes
BFS 2-Coloring	O(V + E)	O(V)	Most common, level-based
DFS 2-Coloring	O(V + E)	O(V)	Recursive or iterative
Union-Find	O(V + E * alpha(V))	O(V)	Nearly linear, elegant

All three approaches visit each vertex and edge exactly once (or near-once for Union-Find with path compression). The space is O(V) for the color array or Union-Find structure.

For a graph with V vertices and E edges:

• Best case: O(V + E) for all approaches, no way to be faster since you must examine every edge.
• Worst case: Same, O(V + E). The algorithm terminates as soon as it finds a conflict, so it can be faster in practice for non-bipartite graphs.

Finding the Two Sets

If you need to actually return the two sets (not just check), collect them from the color array.

def bipartite_sets(graph: list[list[int]]) -> tuple[set, set] | None:
    """
    Return the two sets if bipartite, or None if not.
    """
    n = len(graph)
    color = [-1] * n
    
    for i in range(n):
        if color[i] != -1:
            continue
        queue = deque([i])
        color[i] = 0
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append(nei)
                elif color[nei] == color[node]:
                    return None
    
    set_a = {i for i in range(n) if color[i] == 0}
    set_b = {i for i in range(n) if color[i] == 1}
    return set_a, set_b

Practice Problems

Problem	Difficulty	Key Concept
LeetCode 785: Is Graph Bipartite?	Medium	BFS/DFS 2-coloring
LeetCode 886: Possible Bipartition	Medium	Bipartite as grouping
LeetCode 1042: Flower Planting With No Adjacent	Medium	Graph coloring variant
LeetCode 207: Course Schedule	Medium	Cycle detection (related)
Codeforces: Bipartite Check	Medium	Standard bipartite

Key Takeaways

1. Bipartite = 2-colorable = no odd cycles. These three conditions are equivalent.
2. BFS 2-coloring is the go-to approach. It is intuitive, efficient, and easy to implement.
3. Always handle disconnected components. Loop over all nodes and start BFS/DFS from each unvisited one.
4. The Union-Find approach is a good alternative when you already have Union-Find infrastructure in your solution.
5. Bipartite checking is a building block for matching, scheduling, and many graph partition problems.