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)

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)

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)

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

Start with an empty matching.
Search for an augmenting path.
If one exists, flip the path.
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)

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

Main Idea

Use breadth-first search to construct layered levels.
Find a maximal collection of vertex-disjoint shortest augmenting paths.
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)

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).

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

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.

Prove Berge’s lemma.
Show that every augmenting path increases matching size by exactly one.
Determine the maximum matching size of $K_{4,7}$ .
Prove König’s theorem for a simple example.
Explain why every perfect matching is maximum.
Construct the flow network corresponding to a bipartite matching problem.
Show that a matching corresponds to a collection of matrix entries with no repeated row or column.
Give an example of a maximal matching that is not maximum.
Explain why Hopcroft-Karp is faster than repeatedly augmenting along arbitrary paths.