Chapter 56. Matchings

A matching is a set of edges chosen so that no two chosen edges touch the same vertex. Equivalently, each vertex is used by at most one chosen edge. This simple condition makes matchings a basic model for pairing problems: assigning workers to jobs, students to projects, machines to tasks, or endpoints in a network.

56.1 Definition

Let

G = (V,E)

be an undirected graph. A matching in $G$ is a subset

M \subseteq E

such that no two distinct edges in $M$ have a common endpoint.

Thus, if

e_1, e_2 \in M

and

e_1 \ne e_2,

then

e_1 \cap e_2 = \varnothing.

For example, in the path graph

v_1 - v_2 - v_3 - v_4,

the set

M = \{\{v_1,v_2\}, \{v_3,v_4\}\}

is a matching. The two chosen edges do not share a vertex.

The set

M' = \{\{v_1,v_2\}, \{v_2,v_3\}\}

is not a matching, because both edges use the vertex $v_2$ .

56.2 Matched and Unmatched Vertices

Let $M$ be a matching in $G$ . A vertex $v$ is called matched, or saturated, by $M$ if $v$ is an endpoint of an edge in $M$ . Otherwise, $v$ is called unmatched, or unsaturated.

M = \{\{a,b\}, \{c,d\}\},

then $a,b,c,d$ are matched. Any vertex outside these four vertices is unmatched.

The matching condition says that a matched vertex is incident with exactly one edge of $M$ . It can never be incident with two edges of $M$ .

56.3 Size of a Matching

The size of a matching is the number of edges it contains. It is denoted by

|M|.

If $M$ contains $k$ edges, then it matches exactly $2k$ vertices, since every edge has two endpoints and no endpoints are shared.

Therefore, in a graph with $n$ vertices,

|M| \leq \left\lfloor \frac{n}{2} \right\rfloor.

This upper bound is sharp when the graph contains enough independent edges to pair all vertices, or all but one vertex.

56.4 Maximal Matchings

A matching $M$ is maximal if it cannot be enlarged by adding another edge.

More precisely, $M$ is maximal if there is no edge

e \in E \setminus M

such that

M \cup \{e\}

is still a matching.

A maximal matching is locally complete. Every edge outside $M$ touches at least one vertex already matched by $M$ . Otherwise, that edge could be added.

Maximal means no single extra edge can be inserted. It does not mean largest possible.

For example, in the path

v_1 - v_2 - v_3 - v_4,

the matching

M = \{\{v_2,v_3\}\}

is maximal. No other edge can be added, because both remaining edges touch $v_2$ or $v_3$ .

However, it is not maximum, because

\{\{v_1,v_2\}, \{v_3,v_4\}\}

has size $2$ .

56.5 Maximum Matchings

A matching $M$ is maximum if it has largest possible size among all matchings in $G$ . The size of a maximum matching is called the matching number of $G$ , commonly denoted by

\nu(G).

Thus,

\nu(G) = \max\{|M| : M \text{ is a matching in } G\}.

Every maximum matching is maximal. If a maximum matching were not maximal, one could add an edge and obtain a larger matching, contradicting maximality of its size.

The converse fails. A maximal matching may be smaller than a maximum matching.

This distinction is important in algorithms. A greedy algorithm easily produces a maximal matching, but it may fail to produce a maximum matching.

56.6 Perfect Matchings

A matching $M$ is perfect if every vertex of $G$ is matched by $M$ . A perfect matching is also called a 1-factor in some parts of graph theory.

If $G$ has $n$ vertices and $M$ is perfect, then $n$ must be even and

|M| = \frac{n}{2}.

A perfect matching is automatically maximum, because no matching can contain more than $n/2$ edges.

For example, the cycle $C_4$ has two perfect matchings:

\{\{v_1,v_2\}, \{v_3,v_4\}\}

and

\{\{v_2,v_3\}, \{v_4,v_1\}\}.

The cycle $C_5$ has no perfect matching, because it has an odd number of vertices.

56.7 Near-Perfect Matchings

A matching is near-perfect if it leaves exactly one vertex unmatched.

A near-perfect matching can occur only in a graph with an odd number of vertices. If $G$ has $2k+1$ vertices, then a near-perfect matching has size

k.

For example, the path

v_1 - v_2 - v_3

has two near-perfect matchings:

\{\{v_1,v_2\}\}

and

\{\{v_2,v_3\}\}.

Each leaves exactly one vertex unmatched.

56.8 Matchings in Bipartite Graphs

Matchings are especially important in bipartite graphs.

Let

G = (X \cup Y, E)

be a bipartite graph, where every edge joins a vertex in $X$ to a vertex in $Y$ . A matching pairs vertices of $X$ with vertices of $Y$ .

This is the natural model for assignment problems. The set $X$ may represent workers, and the set $Y$ may represent jobs. An edge $xy$ means worker $x$ is allowed to do job $y$ . A matching chooses compatible assignments so that no worker and no job is used more than once.

A matching that saturates every vertex in $X$ is called an $X$ -saturating matching. It assigns every vertex on the left side to a distinct neighbor on the right side.

A perfect matching in a bipartite graph saturates both sides. Therefore, a bipartite graph with parts $X$ and $Y$ can have a perfect matching only if

|X| = |Y|.

56.9 Alternating Paths

Let $M$ be a matching in $G$ . An alternating path with respect to $M$ is a path whose edges alternate between edges outside $M$ and edges inside $M$ .

For example, a path

v_0v_1v_2v_3v_4

is alternating if

v_0v_1 \notin M,\quad v_1v_2 \in M,\quad v_2v_3 \notin M,\quad v_3v_4 \in M.

Alternating paths describe how a matching can be rearranged. Along such a path, one may remove the matching edges and add the non-matching edges. This operation is called flipping the path.

The matching condition is preserved because the path alternates.

56.10 Augmenting Paths

An augmenting path is an alternating path whose first and last vertices are unmatched.

Suppose the path begins and ends with edges outside $M$ . Then the path contains one more non-matching edge than matching edge. If we flip the path, we remove fewer edges than we add. The size of the matching increases by one.

For example, let

P = v_0v_1v_2v_3

be an alternating path such that

v_0v_1 \notin M,\quad v_1v_2 \in M,\quad v_2v_3 \notin M,

and suppose $v_0$ and $v_3$ are unmatched. Then replacing

\{v_1v_2\}

\{v_0v_1, v_2v_3\}

increases the matching size by one.

Augmenting paths are the basic mechanism behind many matching algorithms.

56.11 Berge’s Lemma

The fundamental theorem behind maximum matchings is Berge’s lemma.

Theorem 56.1. Berge’s Lemma.
A matching $M$ in a graph $G$ is maximum if and only if there is no augmenting path with respect to $M$ .

The forward direction is immediate. If an augmenting path exists, then flipping it produces a larger matching. Hence $M$ cannot be maximum.

The reverse direction is deeper. If $M$ is not maximum, let $N$ be a larger matching. Consider the symmetric difference

M \triangle N = (M \setminus N) \cup (N \setminus M).

In the graph formed by these edges, every vertex has degree at most $2$ , because each of $M$ and $N$ uses any vertex at most once. Therefore, each component is a path or a cycle whose edges alternate between $M$ and $N$ .

Since $N$ has more edges than $M$ , at least one component contains more edges from $N$ than from $M$ . Such a component must be an alternating path that begins and ends with edges from $N$ . Its endpoints are unmatched by $M$ . Hence it is an augmenting path.

Thus the absence of augmenting paths exactly characterizes maximum matchings.

56.12 Greedy Construction of a Maximal Matching

A maximal matching can be found by a simple greedy method.

Start with

M = \varnothing.

Scan the edges of $G$ . Whenever an edge has both endpoints currently unmatched, add it to $M$ . Continue until no more edge can be added.

This always produces a maximal matching. If an unused edge had two unmatched endpoints at the end, the algorithm could still add it.

However, the result depends on the order of the edges. Different orders may produce different maximal matchings.

On the path

v_1 - v_2 - v_3 - v_4,

choosing the middle edge first produces a maximal matching of size $1$ . Choosing the two outer edges produces a maximum matching of size $2$ .

56.13 Approximation by Maximal Matchings

Although a maximal matching may fail to be maximum, it is never too small compared with a maximum matching.

Let $M$ be any maximal matching, and let $M^\ast$ be a maximum matching. Every edge of $M^\ast$ must touch at least one edge of $M$ . Otherwise, that edge could be added to $M$ , contradicting maximality.

Each edge of $M$ has two endpoints, so it can touch at most two edges of $M^\ast$ . Therefore,

|M^\ast| \leq 2|M|.

Hence,

|M| \geq \frac{1}{2}|M^\ast|.

So any maximal matching is a factor- $2$ approximation to a maximum matching. This fact is often useful in algorithmic graph theory, where a quick approximate solution may be sufficient.

56.14 Counting Matched Vertices

If $M$ is a matching, then each edge in $M$ contributes exactly two matched vertices. Therefore, the number of matched vertices is

2|M|.

The number of unmatched vertices is

|V| - 2|M|.

A matching is perfect exactly when this number is zero:

|V| - 2|M| = 0.

A matching is near-perfect exactly when this number is one:

|V| - 2|M| = 1.

These formulas are elementary, but they are useful when checking whether a matching can have a certain form.

56.15 Matching Number

The matching number $\nu(G)$ is the size of a maximum matching.

For a few basic graph families, it can be computed directly.

For the path graph $P_n$ ,

\nu(P_n) = \left\lfloor \frac{n}{2} \right\rfloor.

For the cycle graph $C_n$ ,

\nu(C_n) = \left\lfloor \frac{n}{2} \right\rfloor.

For the complete graph $K_n$ ,

\nu(K_n) = \left\lfloor \frac{n}{2} \right\rfloor.

For the complete bipartite graph $K_{m,n}$ ,

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

These examples show that the matching number is constrained by the number of vertices, but also by the structure of the graph.

56.16 Edge Covers and Matchings

An edge cover is a set of edges such that every vertex is incident with at least one selected edge. Edge covers and matchings are dual in a useful sense for graphs without isolated vertices.

If $G$ has no isolated vertices, then the size of a maximum matching and the size of a minimum edge cover satisfy the Gallai identity:

\nu(G) + \rho(G) = |V|,

where $\rho(G)$ denotes the minimum size of an edge cover.

The reason is intuitive. A maximum matching covers $2\nu(G)$ vertices. Each remaining unmatched vertex can be covered by adding one incident edge. This produces an edge cover of size

\nu(G) + (|V| - 2\nu(G)) = |V| - \nu(G).

Thus,

\rho(G) = |V| - \nu(G).

56.17 Matchings and Vertex Covers in Bipartite Graphs

In bipartite graphs, matchings are closely related to vertex covers.

A vertex cover is a set of vertices that touches every edge. In any graph, every matching gives a lower bound on every vertex cover. Indeed, if $M$ is a matching and $C$ is a vertex cover, then each edge of $M$ must be covered by at least one vertex of $C$ . Since the edges of $M$ are disjoint, these required vertices are distinct. Therefore,

|M| \leq |C|.

For bipartite graphs, König’s theorem says that this lower bound is always tight:

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

This theorem is one of the central min-max results in graph theory. It connects a packing problem, choosing disjoint edges, with a covering problem, choosing vertices that meet all edges.

56.18 Common Types of Matchings

Type	Meaning
Matching	A set of pairwise non-adjacent edges
Maximal matching	A matching that cannot be enlarged by adding one edge
Maximum matching	A matching of largest possible size
Perfect matching	A matching that saturates every vertex
Near-perfect matching	A matching that leaves exactly one vertex unmatched
$X$ -saturating matching	A matching in a bipartite graph that saturates every vertex of $X$

The most common confusion is between maximal and maximum. Maximal is a local condition. Maximum is a global condition.

56.19 Applications

Matchings model situations where objects must be paired without reuse.

In job assignment, vertices on one side represent workers and vertices on the other side represent jobs. A matching assigns workers to jobs.

In scheduling, vertices may represent tasks and time slots. A matching assigns tasks to available slots.

In chemistry, matchings model pairings of atoms or bonds in molecular graphs.

In network design, matchings describe independent communication links that can be active simultaneously.

In algorithms, matchings appear in flow problems, optimization, approximation algorithms, and reductions between graph problems.

The abstraction is useful because it separates the pairing constraint from the details of the application. Once the graph is built, matching theory supplies the language and algorithms.

56.20 Exercises

Let $P_6$ be the path on six vertices. Find a maximum matching and a maximal matching that is not maximum, if one exists.
Prove that every perfect matching is maximum.
Give an example of a graph with a maximal matching of size $1$ and a maximum matching of size $2$ .
Find the matching number of $K_{3,5}$ .
Let $M$ be a matching in $G$ . Prove that the number of matched vertices is $2|M|$ .
Prove that a graph with an odd number of vertices cannot have a perfect matching.
Let $M$ be a maximal matching and $M^\ast$ a maximum matching. Prove that $|M^\ast| \leq 2|M|$ .
In the cycle $C_6$ , list all perfect matchings.
Let $G$ be a bipartite graph with parts $X$ and $Y$ , where $|X| > |Y|$ . Prove that $G$ has no perfect matching.
Explain why an augmenting path increases the size of a matching by exactly one.