# Chapter 59. Bipartite Matching

# Chapter 59. Bipartite Matching

A bipartite matching is a matching in a bipartite graph. Bipartite matching theory studies how vertices in one part of the graph can be paired with vertices in the other part without conflicts. The subject combines combinatorics, graph algorithms, optimization, and linear programming. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Bipartite_graph?utm_source=chatgpt.com))

Bipartite matchings model assignment problems. Workers are assigned to jobs, students to schools, tasks to processors, or resources to requests. The graph encodes compatibility constraints, while the matching represents a valid assignment.

The theory is especially important because bipartite matching problems admit elegant structural theorems and efficient algorithms.

## 59.1 Bipartite Graphs

A graph

$$
G = (X \cup Y,E)
$$

is bipartite if:

$$
X \cap Y = \varnothing,
$$

and every edge joins a vertex in \(X\) to a vertex in \(Y\).

The sets \(X\) and \(Y\) are called the partite sets.

No edge joins two vertices within the same part.

For example,

$$
X=\{x_1,x_2,x_3\},
\qquad
Y=\{y_1,y_2,y_3\},
$$

with edges

$$
x_1y_1,
\quad
x_1y_2,
\quad
x_2y_2,
\quad
x_3y_3
$$

defines a bipartite graph.

Bipartite graphs are characterized by the absence of odd cycles. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Bipartite_graph?utm_source=chatgpt.com))

## 59.2 Matchings in Bipartite Graphs

A matching

$$
M \subseteq E
$$

is a set of edges such that no two edges share a vertex.

In a bipartite graph, a matching pairs vertices from \(X\) with vertices from \(Y\).

Each vertex can participate in at most one chosen edge.

For example,

$$
M=
\{
x_1y_1,
x_2y_2,
x_3y_3
\}
$$

is a matching if the three edges are distinct and vertex-disjoint.

The matching is perfect if every vertex is matched.

The matching saturates \(X\) if every vertex in \(X\) is matched.

## 59.3 Maximum Bipartite Matching

A maximum bipartite matching is a matching of largest possible size.

Its size is denoted by

$$
\nu(G).
$$

The problem of finding a maximum matching is one of the fundamental optimization problems in graph theory.

Unlike general matching problems, bipartite matching has especially clean structure. Hall's theorem characterizes existence, and augmenting-path algorithms solve the optimization problem efficiently.

## 59.4 Augmenting Paths

Let \(M\) be a matching in a bipartite graph \(G\).

An alternating path is a path whose edges alternate between belonging to \(M\) and not belonging to \(M\).

An augmenting path is an alternating path that begins and ends at unmatched vertices.

For example,

$$
x_1y_1x_2y_2x_3
$$

may alternate:

| Edge | Status |
|---|---|
| \(x_1y_1\) | not in \(M\) |
| \(y_1x_2\) | in \(M\) |
| \(x_2y_2\) | not in \(M\) |
| \(y_2x_3\) | in \(M\) |

If the first and last vertices are unmatched, then flipping the edges along the path increases the matching size by one.

This operation replaces matching edges by nonmatching edges and vice versa.

## 59.5 Berge's Lemma

The key theorem behind matching algorithms is Berge's lemma.

**Theorem 59.1. Berge's Lemma.**  
A matching \(M\) is maximum if and only if there exists no augmenting path with respect to \(M\). ([en.wikipedia.org](https://en.wikipedia.org/wiki/Berge%27s_lemma?utm_source=chatgpt.com))

This theorem transforms the matching problem into a path-search problem.

### Proof Sketch

If an augmenting path exists, flipping the path increases the matching size by one, so \(M\) cannot be maximum.

Conversely, suppose \(M\) is not maximum. Let \(N\) be a larger matching.

Consider the symmetric difference

$$
M \triangle N.
$$

Every connected component of this graph is either:

| Component | Structure |
|---|---|
| Even cycle | Alternating |
| Alternating path | Edges alternate |
| Isolated vertex | Degree \(0\) |

Since \(N\) has more edges than \(M\), some component contains more edges from \(N\) than from \(M\). Such a component must be an augmenting path.

Therefore, the absence of augmenting paths characterizes maximum matchings.

## 59.6 Alternating Trees

Many matching algorithms build alternating trees.

Start from an unmatched vertex in \(X\). Explore alternating paths by:

| Step | Edge Type |
|---|---|
| From unmatched level | Nonmatching edge |
| From matched level | Matching edge |

The resulting structure alternates between unmatched and matched edges.

Alternating trees search systematically for augmenting paths.

If an unmatched vertex in \(Y\) becomes reachable, an augmenting path has been found.

## 59.7 The Hungarian Perspective

Bipartite matching can be interpreted as an assignment problem.

Suppose:

| Set | Meaning |
|---|---|
| \(X\) | Workers |
| \(Y\) | Jobs |
| Edge \(xy\) | Worker \(x\) can perform job \(y\) |

A matching assigns workers to distinct jobs.

A perfect matching assigns every worker exactly one job and every job exactly one worker.

Weighted versions assign costs or profits to edges and seek optimal assignments. These lead to the Hungarian algorithm and linear optimization theory.

## 59.8 Hall's Theorem Revisited

Hall's theorem completely characterizes when a bipartite graph contains a matching saturating \(X\).

**Theorem 59.2. Hall's Theorem.**  
A bipartite graph

$$
G=(X \cup Y,E)
$$

contains a matching saturating \(X\) if and only if for every subset

$$
A \subseteq X,
$$

$$
|N(A)| \ge |A|.
$$

|N(A)| \ge |A|

Hall's theorem is the structural foundation of bipartite matching theory.

## 59.9 Maximum Matching Algorithms

The simplest algorithm repeatedly searches for augmenting paths.

### Augmenting-Path Algorithm

1. Start with an empty matching.
2. Search for an augmenting path.
3. If one exists, flip the path.
4. Repeat until no augmenting path exists.

By Berge's lemma, the final matching is maximum.

### Complexity

If each augmenting path search uses breadth-first search or depth-first search, then the running time is polynomial.

More advanced algorithms improve efficiency substantially.

## 59.10 The Hopcroft-Karp Algorithm

The Hopcroft-Karp algorithm is the standard algorithm for maximum bipartite matching. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm?utm_source=chatgpt.com))

Instead of augmenting one path at a time, the algorithm finds many shortest augmenting paths simultaneously.

### Main Idea

1. Use breadth-first search to construct layered levels.
2. Find a maximal collection of vertex-disjoint shortest augmenting paths.
3. Augment along all of them simultaneously.

This greatly reduces the number of augmentation phases.

### Complexity

The Hopcroft-Karp algorithm runs in

$$
O(E\sqrt{V}).
$$

This is significantly faster than naive augmenting-path algorithms for large sparse graphs.

## 59.11 Bipartite Matching as Flow

Bipartite matching can be transformed into a network flow problem.

Construct a directed network:

| Edge | Capacity |
|---|---|
| Source to each \(x \in X\) | \(1\) |
| Each edge \(xy\) | \(1\) |
| Each \(y \in Y\) to sink | \(1\) |

A matching corresponds to an integer flow.

Each selected matching edge carries one unit of flow.

A maximum matching corresponds exactly to a maximum flow.

Thus bipartite matching is a special case of network flow.

## 59.12 König's Theorem

One of the deepest results about bipartite graphs is König's theorem.

A vertex cover is a set of vertices touching every edge.

**Theorem 59.3. König's Theorem.**  
In every bipartite graph,

$$
\text{maximum matching size} =
\text{minimum vertex cover size}.
$$

([en.wikipedia.org](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_%28graph_theory%29?utm_source=chatgpt.com))

This theorem is remarkable because it connects:

| Problem | Type |
|---|---|
| Maximum matching | Packing problem |
| Minimum vertex cover | Covering problem |

In arbitrary graphs, these quantities need not be equal.

## 59.13 Proof Idea of König's Theorem

Let \(M\) be a maximum matching.

Build alternating trees from unmatched vertices in \(X\).

Define:

| Set | Meaning |
|---|---|
| \(Z_X\) | Reachable vertices in \(X\) |
| \(Z_Y\) | Reachable vertices in \(Y\) |

Then the set

$$
(X \setminus Z_X) \cup Z_Y
$$

forms a minimum vertex cover.

Its size equals

$$
|M|.
$$

Thus:

$$
\text{minimum vertex cover size}
\le
|M|.
$$

Since every vertex cover must contain at least one endpoint of each matching edge,

$$
|M|
\le
\text{minimum vertex cover size}.
$$

Equality follows.

## 59.14 Weighted Bipartite Matching

In weighted matching problems, each edge has weight or cost.

The goal becomes:

| Objective | Meaning |
|---|---|
| Maximum-weight matching | Maximize total weight |
| Minimum-cost matching | Minimize total cost |

These problems arise in scheduling, transportation, and assignment optimization.

The Hungarian algorithm solves the weighted assignment problem in polynomial time.

## 59.15 Complete Bipartite Graphs

The complete bipartite graph

$$
K_{m,n}
$$

contains every possible edge between \(X\) and \(Y\).

Its maximum matching size is

$$
\nu(K_{m,n})=\min(m,n).
$$

If

$$
m=n,
$$

then the graph contains a perfect matching.

Indeed, any bijection between \(X\) and \(Y\) defines one.

## 59.16 Matchings and Matrix Theory

Let \(G\) be bipartite with adjacency matrix

$$
A=(a_{ij}).
$$

A matching corresponds to selecting entries equal to \(1\) such that no two chosen entries lie in the same row or column.

A perfect matching corresponds to a permutation matrix embedded in \(A\).

Thus bipartite matching connects graph theory with matrix combinatorics.

The permanent of the adjacency matrix counts perfect matchings.

## 59.17 Stable Matchings

Classical bipartite matching studies compatibility only.

Stable matching introduces preferences.

Each vertex ranks its possible partners. A matching is stable if no unmatched pair prefers each other over their assigned partners.

This leads to the Gale-Shapley stable marriage algorithm.

Stable matching differs fundamentally from maximum matching because the objective concerns preference stability rather than cardinality.

## 59.18 Applications

Bipartite matching appears in many domains.

| Application | Interpretation |
|---|---|
| Job assignment | Workers matched to jobs |
| Course registration | Students matched to classes |
| Scheduling | Tasks matched to machines |
| Organ donation | Donors matched to recipients |
| Network routing | Requests matched to channels |
| Computer vision | Feature correspondence |
| Recommendation systems | Users matched to items |

The mathematical abstraction is simple, but its practical reach is extremely broad.

## 59.19 Common Types of Bipartite Matching Problems

| Problem | Goal |
|---|---|
| Maximum matching | Largest number of matched pairs |
| Perfect matching | Match every vertex |
| Weighted matching | Optimize total weight |
| Stable matching | Respect preference structure |
| Online matching | Decisions made incrementally |

These variants form a major part of combinatorial optimization.

## 59.20 Exercises

1. Find a maximum matching in the graph:

$$
X=\{x_1,x_2,x_3\},
\qquad
Y=\{y_1,y_2,y_3\},
$$

with edges

$$
x_1y_1,
\quad
x_1y_2,
\quad
x_2y_2,
\quad
x_3y_2,
\quad
x_3y_3.
$$

2. Prove Berge's lemma.

3. Show that every augmenting path increases matching size by exactly one.

4. Determine the maximum matching size of \(K_{4,7}\).

5. Prove König's theorem for a simple example.

6. Explain why every perfect matching is maximum.

7. Construct the flow network corresponding to a bipartite matching problem.

8. Show that a matching corresponds to a collection of matrix entries with no repeated row or column.

9. Give an example of a maximal matching that is not maximum.

10. Explain why Hopcroft-Karp is faster than repeatedly augmenting along arbitrary paths.