Bipartite Graph: Checking and Applications

Key Insights

A graph is bipartite if and only if it contains no odd-length cycles, which means you can verify bipartiteness through simple two-coloring algorithms using BFS or DFS in O(V+E) time.
The choice between BFS, DFS, and Union-Find for bipartite checking depends on your specific constraints: BFS provides intuitive level-based coloring, DFS offers natural recursion for tree-like structures, and Union-Find excels when you’re already maintaining connected components.
Maximum bipartite matching powers critical real-world systems from job assignment platforms to hospital residency matching, making bipartite graph algorithms essential knowledge for systems designers.

Introduction to Bipartite Graphs

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. No edge exists between vertices within the same set.

Think of it this way: you have two groups of entities, and relationships only exist across groups, never within them. Students and courses. Workers and jobs. Users and products they’ve purchased.

The fundamental theorem that makes bipartite graphs tractable: a graph is bipartite if and only if it contains no odd-length cycles. This gives us a practical verification strategy. If you can traverse the graph and assign alternating “colors” to adjacent nodes without conflict, the graph is bipartite. If you find two adjacent nodes that must share the same color, you’ve discovered an odd cycle.

This property transforms an abstract mathematical concept into something you can check algorithmically. Let’s examine three approaches.

Checking Bipartiteness with BFS

The BFS approach treats bipartite verification as a two-coloring problem. Start from any unvisited node, assign it color 0, then assign color 1 to all neighbors, color 0 to their neighbors, and so on. If you ever try to color a node that’s already colored with the opposite color, the graph isn’t bipartite.

from collections import deque

def is_bipartite_bfs(graph: dict[int, list[int]]) -> tuple[bool, dict[int, int]]:
    """
    Check if graph is bipartite using BFS two-coloring.
    Returns (is_bipartite, color_assignment).
    Graph is adjacency list: {node: [neighbors]}
    """
    color = {}
    
    for start in graph:
        if start in color:
            continue
            
        # BFS from this component's starting node
        queue = deque([start])
        color[start] = 0
        
        while queue:
            node = queue.popleft()
            current_color = color[node]
            next_color = 1 - current_color
            
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = next_color
                    queue.append(neighbor)
                elif color[neighbor] == current_color:
                    # Conflict: adjacent nodes have same color
                    return False, {}
    
    return True, color


# Example usage
graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

is_bip, coloring = is_bipartite_bfs(graph)
print(f"Bipartite: {is_bip}")  # True
print(f"Coloring: {coloring}")  # {0: 0, 1: 1, 2: 0, 3: 1}

The outer loop handles disconnected components. Each component gets its own BFS traversal. This is critical—forgetting disconnected components is a common bug.

BFS naturally processes nodes level by level, making the alternating color assignment intuitive. Nodes at even distances from the start get color 0; odd distances get color 1.

Checking Bipartiteness with DFS

DFS achieves the same result through recursive exploration. The logic is identical—assign alternating colors—but the traversal order differs.

def is_bipartite_dfs(graph: dict[int, list[int]]) -> tuple[bool, dict[int, int]]:
    """
    Check if graph is bipartite using DFS two-coloring.
    Returns (is_bipartite, color_assignment).
    """
    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 start in graph:
        if start not in color:
            if not dfs(start, 0):
                return False, {}
    
    return True, color


# Test with an odd cycle (not bipartite)
triangle = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}

is_bip, _ = is_bipartite_dfs(triangle)
print(f"Triangle is bipartite: {is_bip}")  # False

DFS has a subtle advantage when you need to extract the actual odd cycle as proof of non-bipartiteness. The recursive call stack naturally contains the path, making cycle reconstruction straightforward.

def find_odd_cycle(graph: dict[int, list[int]]) -> list[int] | None:
    """
    If graph is not bipartite, return an odd cycle. Otherwise None.
    """
    color = {}
    parent = {}
    
    def dfs(node: int, c: int) -> list[int] | None:
        color[node] = c
        for neighbor in graph[node]:
            if neighbor not in color:
                parent[neighbor] = node
                cycle = dfs(neighbor, 1 - c)
                if cycle is not None:
                    return cycle
            elif color[neighbor] == c:
                # Found odd cycle - reconstruct it
                cycle = [neighbor, node]
                current = node
                while current != neighbor:
                    current = parent.get(current)
                    if current is None:
                        break
                    cycle.append(current)
                return cycle
        return None
    
    for start in graph:
        if start not in color:
            parent[start] = None
            cycle = dfs(start, 0)
            if cycle:
                return cycle
    return None

Union-Find Approach

Union-Find offers an alternative perspective. Instead of coloring, we track which nodes must be in opposite sets. For each edge (u, v), nodes u and v must be in different partitions.

The trick: for each node n, we create a virtual node n’ representing “the opposite partition of n.” When we see edge (u, v), we union u with v’ and v with u’. If u and u’ ever end up in the same set, we have a contradiction.

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> None:
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        # Union by rank
        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_union_find(n: int, edges: list[tuple[int, int]]) -> bool:
    """
    Check bipartiteness using Union-Find.
    n: number of nodes (0 to n-1)
    edges: list of (u, v) pairs
    
    We use nodes 0..n-1 for one "side" and n..2n-1 for the "opposite" side.
    Node i's opposite is i + n.
    """
    uf = UnionFind(2 * n)
    
    for u, v in edges:
        # u and v must be in opposite partitions
        # So: union(u, v's opposite) and union(v, u's opposite)
        uf.union(u, v + n)
        uf.union(v, u + n)
        
        # Check if any node is in same set as its opposite
        if uf.find(u) == uf.find(u + n) or uf.find(v) == uf.find(v + n):
            return False
    
    return True


# Example
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
print(is_bipartite_union_find(4, edges))  # True

edges_triangle = [(0, 1), (1, 2), (2, 0)]
print(is_bipartite_union_find(3, edges_triangle))  # False

Union-Find shines when edges arrive incrementally and you need to maintain bipartiteness dynamically. It’s also useful when you’re already using Union-Find for connectivity queries.

Maximum Bipartite Matching

Once you’ve verified a graph is bipartite, the next question is often: what’s the maximum matching? A matching is a set of edges with no shared vertices. Maximum matching finds the largest such set.

The classic approach uses augmenting paths. An augmenting path starts at an unmatched vertex in set A, alternates between unmatched and matched edges, and ends at an unmatched vertex in set B. Finding and applying augmenting paths increases the matching size by one.

def max_bipartite_matching(
    left_nodes: int, 
    right_nodes: int, 
    edges: list[tuple[int, int]]
) -> list[tuple[int, int]]:
    """
    Find maximum matching in bipartite graph.
    left_nodes: count of nodes in left partition (0 to left_nodes-1)
    right_nodes: count of nodes in right partition (0 to right_nodes-1)
    edges: list of (left_node, right_node) pairs
    
    Returns list of matched (left, right) pairs.
    """
    # Build adjacency list for left nodes
    adj = [[] for _ in range(left_nodes)]
    for u, v in edges:
        adj[u].append(v)
    
    # match_right[v] = u means right node v is matched to left node u
    match_right = [-1] * right_nodes
    
    def find_augmenting_path(u: int, visited: set) -> bool:
        for v in adj[u]:
            if v in visited:
                continue
            visited.add(v)
            
            # If v is unmatched, or we can find augmenting path from v's match
            if match_right[v] == -1 or find_augmenting_path(match_right[v], visited):
                match_right[v] = u
                return True
        return False
    
    matching_size = 0
    for u in range(left_nodes):
        visited = set()
        if find_augmenting_path(u, visited):
            matching_size += 1
    
    # Extract matching
    result = []
    for v, u in enumerate(match_right):
        if u != -1:
            result.append((u, v))
    
    return result


# Job assignment: 3 workers, 4 jobs
# Worker 0 can do jobs 0, 1
# Worker 1 can do jobs 1, 2
# Worker 2 can do jobs 2, 3
edges = [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3)]
matching = max_bipartite_matching(3, 4, edges)
print(f"Maximum matching: {matching}")  # [(0, 0), (1, 1), (2, 2)] or similar

This simple algorithm runs in O(V × E) time. For better performance on large graphs, Hopcroft-Karp achieves O(E × √V) by finding multiple augmenting paths per iteration.

Real-World Applications

Job Assignment: Given workers with different skills and jobs requiring specific skills, find the maximum number of jobs that can be assigned (one worker per job). This is exactly maximum bipartite matching.

Hospital Residency Matching: The National Resident Matching Program uses a variant called stable matching. Medical students and hospitals rank each other, and the algorithm finds a stable assignment where no student-hospital pair would both prefer each other over their current matches.

Recommendation Systems: User-item interaction graphs are naturally bipartite. Users form one partition, items the other. Edges represent purchases, views, or ratings. Graph algorithms on this structure power collaborative filtering.

Course Scheduling: Students and time slots form a bipartite graph. Edges represent availability. Finding a valid schedule means finding a matching that covers all students (or maximizes coverage).

Complexity Analysis and Trade-offs

All three bipartite checking algorithms run in O(V + E) time and O(V) space for the color/parent arrays.

Choose BFS when: You want intuitive, iterative code. BFS is also preferable when you need the shortest path to a conflict (the odd cycle with minimum edges from the start).

Choose DFS when: You’re working with recursive structures or need to extract the full odd cycle. DFS also integrates naturally with other DFS-based algorithms you might be running.

Choose Union-Find when: Edges arrive dynamically, you need to answer bipartiteness queries incrementally, or you’re already maintaining Union-Find for connectivity. The amortized cost per operation is nearly O(1) with path compression and union by rank.

For maximum matching, the simple augmenting path algorithm suffices for graphs with thousands of edges. Beyond that, implement Hopcroft-Karp or reduce to maximum flow using algorithms like Dinic’s.

Bipartite graphs appear everywhere in practical systems. The algorithms are straightforward once you internalize the two-coloring intuition. Master these patterns, and you’ll recognize bipartite structure in problems that don’t explicitly mention graphs at all.