9.14 Bipartite Graphs

You need to divide vertices into two groups such that every edge connects vertices from different groups.

algorithmsgraphsgraph-theory

9.14 Bipartite Graphs

Problem

You need to divide vertices into two groups such that every edge connects vertices from different groups.

Many real-world systems naturally have this structure:

  • Students and courses
  • Workers and jobs
  • Users and roles
  • Buyers and products
  • Actors and movies
  • Customers and orders

The vertices belong to two distinct categories, and relationships exist only across categories.

You need a way to recognize and validate this structure.

Solution

Use a bipartite graph.

A graph is bipartite if its vertices can be partitioned into two disjoint sets:

Left
Right

such that every edge connects one vertex from the left set to one vertex from the right set.

Example:

A     X
| \   |
|  \  |
|   \ |
B     Y

Possible partition:

Left  = {A, B}
Right = {X, Y}

No edge connects:

A ↔ B

or:

X ↔ Y

The graph is bipartite.

The standard detection algorithm uses BFS or DFS coloring.

Discussion

Bipartite graphs appear so frequently that they deserve special treatment.

Many optimization problems become dramatically easier once a graph is known to be bipartite.

Examples include:

  • Maximum matching
  • Assignment problems
  • Scheduling
  • Resource allocation
  • Recommendation systems
  • Network flow modeling

A surprising number of apparently unrelated problems can be transformed into bipartite graphs.

Recognizing the pattern is an important algorithmic skill.

Two-Color Interpretation

A graph is bipartite if and only if it can be colored using two colors.

Suppose:

Red
Blue

are available.

Every edge must connect vertices of different colors.

Example:

A --- B
|     |
D --- C

Valid coloring:

A = Red
B = Blue
C = Red
D = Blue

Every edge crosses between colors.

The graph is bipartite.

This observation immediately suggests an algorithm.

Traverse the graph.

Assign alternating colors.

If a conflict occurs, the graph is not bipartite.

Why Odd Cycles Matter

Consider:

A --- B
 \   /
   C

This triangle contains three vertices.

Attempt coloring:

A = Red
B = Blue

Then:

C must differ from A

so:

C = Blue

But now:

B --- C

connects two blue vertices.

Conflict.

The graph cannot be bipartite.

This example illustrates a fundamental theorem:

A graph is bipartite if and only if it contains no odd-length cycle.

This characterization is one of the most important facts about bipartite graphs.

Recipe: BFS Bipartite Test

The standard implementation uses BFS.

from collections import deque

def is_bipartite(graph):
    color = {}

    for start in graph:
        if start in color:
            continue

        color[start] = 0

        queue = deque([start])

        while queue:
            vertex = queue.popleft()

            for neighbor in graph[vertex]:
                if neighbor not in color:
                    color[neighbor] = (
                        1 - color[vertex]
                    )

                    queue.append(neighbor)

                elif (
                    color[neighbor]
                    == color[vertex]
                ):
                    return False

    return True

Example:

graph = {
    "A": ["B", "D"],
    "B": ["A", "C"],
    "C": ["B", "D"],
    "D": ["A", "C"],
}

Result:

True

The graph is bipartite.

Why BFS Coloring Works

Recall that BFS discovers vertices by layers.

Suppose:

A
|
B
|
C
|
D

Layer assignment:

Vertex Distance
A 0
B 1
C 2
D 3

Even layers receive one color.

Odd layers receive the other.

Even = Red
Odd  = Blue

Every edge connects adjacent layers.

Therefore every edge connects opposite colors.

A conflict can occur only when an odd cycle exists.

DFS Version

DFS works equally well.

def is_bipartite(graph):
    color = {}

    def dfs(vertex, current_color):
        color[vertex] = current_color

        for neighbor in graph[vertex]:
            if neighbor not in color:
                if not dfs(
                    neighbor,
                    1 - current_color
                ):
                    return False

            elif (
                color[neighbor]
                == current_color
            ):
                return False

        return True

    for vertex in graph:
        if vertex not in color:
            if not dfs(vertex, 0):
                return False

    return True

The complexity is identical to BFS.

The choice is largely stylistic.

Recipe: Produce the Two Partitions

Sometimes the partition itself is needed.

from collections import deque

def bipartition(graph):
    color = {}

    for start in graph:
        if start in color:
            continue

        color[start] = 0

        queue = deque([start])

        while queue:
            vertex = queue.popleft()

            for neighbor in graph[vertex]:
                if neighbor not in color:
                    color[neighbor] = (
                        1 - color[vertex]
                    )

                    queue.append(neighbor)

                elif (
                    color[neighbor]
                    == color[vertex]
                ):
                    return None

    left = [
        v
        for v, c in color.items()
        if c == 0
    ]

    right = [
        v
        for v, c in color.items()
        if c == 1
    ]

    return left, right

Example:

(
    ["A", "C"],
    ["B", "D"]
)

This output is often used by matching algorithms.

Detecting Odd Cycles

A failed coloring implies an odd cycle.

Consider:

A
|\\n| \\nB--C

Traversal might produce:

A = Red
B = Blue
C = Blue

The edge:

B -- C

creates a conflict.

Both endpoints have the same color.

The graph therefore contains an odd cycle.

Many bipartite-testing implementations report the offending edge for debugging purposes.

Modeling Relationships

Bipartite graphs are often hidden inside business problems.

Students and Courses

Student → Course

Partition:

Students
Courses

Users and Roles

User → Role

Partition:

Users
Roles

Customers and Products

Customer → Product

Partition:

Customers
Products

Whenever entities naturally belong to two categories, consider a bipartite model.

Complete Bipartite Graphs

A complete bipartite graph connects every vertex in one partition to every vertex in the other.

Notation:

K(m,n)

Example:

K(2,3)

contains:

2 left vertices
3 right vertices

with all possible cross-partition edges.

Visualized:

A ---- X
| \  / |
|  \/  |
|  /\  |
| /  \ |
B ---- Y
 \    /
  \  /
   Z

Number of edges:

m × n

Complete bipartite graphs frequently appear in matching theory.

Bipartite Matching Preview

One reason bipartite graphs are important is matching.

Example:

Workers ↔ Jobs

Goal:

Assign workers to jobs

Graph:

Worker1 → JobA
Worker1 → JobB

Worker2 → JobA

Worker3 → JobB

This becomes a maximum matching problem.

Efficient solutions exist specifically because the graph is bipartite.

Chapter 12 explores these algorithms in depth.

Complexity Analysis

Let:

  • V = number of vertices
  • E = number of edges

BFS coloring:

Operation Complexity
Bipartite test O(V + E)
Construct partitions O(V + E)
Memory usage O(V)

Every vertex is colored once.

Every edge is examined once.

The algorithm is linear in graph size.

Common Pitfalls

Do not assume every graph can be bipartitioned.

Triangles immediately violate bipartiteness.

Do not forget disconnected components.

A graph may contain several independent regions.

Do not stop after coloring a single component.

Do not confuse bipartite graphs with directed graphs.

Bipartiteness is primarily an undirected graph concept.

Do not assume equal partition sizes.

A valid bipartite graph may have:

1 vertex on one side
1000 vertices on the other

Do not ignore self-loops.

A -- A

immediately violates bipartiteness.

The vertex would need two different colors simultaneously.

Recipe: Validate a Resource Assignment Graph

Suppose:

graph = {
    "Alice": ["Task1", "Task2"],
    "Bob": ["Task1"],
    "Carol": ["Task2"],
    "Task1": ["Alice", "Bob"],
    "Task2": ["Alice", "Carol"],
}

Running:

is_bipartite(graph)

returns:

True

The graph separates naturally into:

People
Tasks

This validation often precedes matching and scheduling algorithms.

Takeaway

Bipartite graphs divide vertices into two groups such that every edge crosses between groups. They can be recognized through two-coloring and are characterized by the absence of odd cycles. Bipartite structure appears naturally in assignment, scheduling, recommendation, and matching problems. Because many difficult graph problems become significantly easier on bipartite graphs, recognizing and validating this structure is an important skill in algorithm design.