Chapter 57. Perfect Matchings

A perfect matching is a matching that covers every vertex of a graph. Every vertex belongs to exactly one selected edge. Perfect matchings represent complete pairings without omission. They appear in scheduling, assignment problems, network design, chemistry, combinatorics, and statistical physics. (en.wikipedia.org)

Perfect matchings form one of the central subjects of matching theory. Their existence depends on both local and global structure. Some graphs admit many perfect matchings. Others admit none, even when every vertex has large degree.

57.1 Definition

Let

G = (V,E)

be a graph. A matching

M \subseteq E

is called a perfect matching if every vertex of $G$ is incident with exactly one edge of $M$ .

Equivalently,

\forall v \in V, \quad \deg_M(v) = 1.

Every vertex is matched once and only once.

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

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

Thus a graph can have a perfect matching only if the number of vertices is even.

For example, the cycle

C_4

has perfect matchings:

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

and

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

The cycle

C_5

cannot have a perfect matching because it contains an odd number of vertices.

57.2 Necessary Conditions

Several immediate conditions are necessary for a graph to possess a perfect matching.

Even Number of Vertices

If $M$ is perfect, then every edge of $M$ covers two vertices, and the matched vertices partition the vertex set. Therefore,

|V|

must be even.

This condition alone is far from sufficient.

The graph consisting of a path on four vertices and an isolated vertex removed still has an even number of vertices, but it may fail to contain a perfect matching because some vertices cannot be paired.

No Isolated Vertices

A graph with an isolated vertex cannot have a perfect matching.

\deg(v)=0,

then no edge is incident with $v$ , so no matching can cover $v$ .

Thus every vertex must have degree at least one.

57.3 Perfect Matchings in Basic Graph Families

Perfect matchings can often be determined explicitly for standard graph families.

Complete Graphs

The complete graph $K_n$ has a perfect matching exactly when $n$ is even.

n = 2k,

pair the vertices arbitrarily into $k$ disjoint pairs.

Thus,

K_{2k}

always has a perfect matching.

Paths

The path graph $P_n$ has a perfect matching exactly when $n$ is even.

P_{2k} = v_1v_2\cdots v_{2k},

then

\{\{v_1,v_2\}, \{v_3,v_4\}, \ldots, \{v_{2k-1},v_{2k}\}\}

is a perfect matching.

Cycles

The cycle graph $C_n$ has a perfect matching exactly when $n$ is even.

An odd cycle necessarily leaves one vertex unmatched.

Complete Bipartite Graphs

The graph

K_{m,n}

has a perfect matching exactly when

m=n.

Each edge joins one vertex from each part, so both parts must contain the same number of vertices.

m=n,

then every bijection between the two parts defines a perfect matching.

57.4 Alternating Cycles

Let $M$ be a perfect matching in $G$ .

An alternating cycle is a cycle whose edges alternate between belonging to $M$ and not belonging to $M$ .

For example,

e_1 \in M, \quad e_2 \notin M, \quad e_3 \in M, \quad e_4 \notin M.

If one flips the status of every edge along such a cycle, removing matching edges and inserting non-matching edges, the result is again a perfect matching.

This operation preserves the property that every vertex is matched exactly once.

Alternating cycles therefore generate new perfect matchings from old ones.

57.5 Uniqueness of Perfect Matchings

A graph may have:

Situation	Meaning
No perfect matching	Complete pairing impossible
One perfect matching	Pairing uniquely determined
Many perfect matchings	Multiple compatible pairings

For example, the path

P_4

has a unique perfect matching:

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

The cycle

C_4

has two distinct perfect matchings.

The complete graph

K_{2n}

has many perfect matchings.

The number of perfect matchings in $K_{2n}$ equals

(2n-1)(2n-3)\cdots 3 \cdot 1.

This is the double factorial

(2n-1)!!.

57.6 Perfect Matchings and Degree Conditions

Large vertex degrees often force the existence of perfect matchings.

One important result is Petersen’s theorem.

Theorem 57.1. Petersen’s Theorem.
Every regular graph of positive even degree with no bridges has a perfect matching. (en.wikipedia.org)

In particular, every cubic bridgeless graph contains a perfect matching.

This theorem is fundamental in structural graph theory and appears in the study of network design and edge coloring.

Another important result concerns bipartite graphs and appears in the next chapter as Hall’s marriage theorem.

57.7 Perfect Matchings and Components

Perfect matchings strongly constrain the structure of components.

Suppose $G$ has a perfect matching $M$ . Let $S \subseteq V(G)$ . Removing $S$ may split the graph into several connected components.

Each odd component of

G-S

must contain at least one vertex matched to a vertex of $S$ . Otherwise, that odd component would need a perfect matching internally, which is impossible because it contains an odd number of vertices.

This observation leads to Tutte’s theorem.

57.8 Tutte’s Theorem

Tutte’s theorem completely characterizes graphs with perfect matchings.

For a graph $G$ , let

o(G-S)

denote the number of odd connected components of $G-S$ .

Theorem 57.2. Tutte’s Theorem.
A graph $G$ has a perfect matching if and only if for every subset

S \subseteq V(G),

the number of odd components of

G-S

satisfies

o(G-S) \leq |S|.

(en.wikipedia.org)

This theorem is one of the deepest results in matching theory.

Intuition

Suppose removing $S$ produces many odd components.

Every odd component requires at least one matching edge connecting it to $S$ , because odd graphs cannot be perfectly matched internally.

If there are more odd components than vertices in $S$ , then there are not enough vertices in $S$ to connect to all odd components. A perfect matching becomes impossible.

Tutte’s theorem states that this obstruction is the only obstruction.

57.9 Factor-Critical Graphs

A graph $G$ is factor-critical if removing any single vertex leaves a graph with a perfect matching.

Formally,

\forall v \in V(G), \quad G-v

has a perfect matching.

Odd cycles provide simple examples.

If one removes any vertex from

C_{2k+1},

the remaining graph is a path with an even number of vertices, hence it has a perfect matching.

Factor-critical graphs appear naturally in the decomposition theory associated with maximum matchings.

57.10 Perfect Matchings in Bipartite Graphs

Perfect matchings in bipartite graphs have a particularly elegant theory.

Let

G = (X \cup Y, E)

be bipartite.

A perfect matching exists only if

|X| = |Y|.

However, equal size alone is insufficient.

The graph

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

with edges

x_1y_1, \quad x_2y_1

has no perfect matching because both vertices in $X$ compete for the same vertex in $Y$ .

Hall’s theorem gives the exact condition.

57.11 Hall’s Condition

For a subset

A \subseteq X,

let

N(A)

denote the set of neighbors of vertices in $A$ .

Hall’s condition states:

|N(A)| \geq |A|

for every subset

A \subseteq X.

Intuitively, every group of vertices on the left must collectively have enough available neighbors on the right.

Hall’s theorem states that this condition is equivalent to the existence of an $X$ -saturating matching.

When

|X|=|Y|,

it becomes equivalent to the existence of a perfect matching.

The next chapter develops this theorem systematically.

57.12 Perfect Matchings and Matrix Theory

Perfect matchings are closely connected to matrices.

Let $G$ be a bipartite graph with parts

X = \{x_1,\ldots,x_n\}, \qquad Y = \{y_1,\ldots,y_n\}.

Its bipartite adjacency matrix is

A = (a_{ij}),

where

a_{ij} = \begin{cases} 1, & x_i y_j \in E, \\ 0, & \text{otherwise}. \end{cases}

A perfect matching corresponds exactly to a permutation matrix contained inside $A$ .

Equivalently, a perfect matching corresponds to a nonzero term in the permanent of $A$ .

This connection links graph theory with combinatorics, algebra, and optimization.

57.13 Perfect Matchings and Chemistry

Perfect matchings play a major role in chemical graph theory.

In molecular graphs representing hydrocarbons, perfect matchings correspond to Kekulé structures. These structures describe arrangements of alternating single and double bonds.

For benzene, multiple perfect matchings correspond to resonance structures.

This connection motivated much early research on matchings and counting perfect matchings.

57.14 Counting Perfect Matchings

Determining whether a perfect matching exists is usually easier than counting how many perfect matchings exist.

For general graphs, counting perfect matchings is computationally difficult.

For bipartite graphs, the count equals the permanent of the adjacency matrix:

\operatorname{perm}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i,\sigma(i)}.

This expression resembles the determinant, except that all signs are positive.

Unlike determinants, permanents are generally hard to compute efficiently.

57.15 Perfect Matchings and Algorithms

Many matching algorithms search for augmenting paths.

Starting from a matching $M$ , an augmenting path increases the size of the matching by one. Repeated augmentation eventually produces a maximum matching.

If the graph has a perfect matching, the algorithm terminates with one.

For bipartite graphs, augmenting-path algorithms are especially efficient. For general graphs, odd cycles introduce additional complications, handled by blossom algorithms developed by Edmonds.

Matching theory became one of the foundations of combinatorial optimization partly because efficient algorithms exist for these problems.

57.16 Deficiency

The deficiency of a graph measures how far the graph is from having a perfect matching.

\nu(G)

is the size of a maximum matching, define

\operatorname{def}(G) = |V(G)| - 2\nu(G).

This equals the number of unmatched vertices left by a maximum matching.

Thus:

Deficiency	Interpretation
$0$	Perfect matching exists
$1$	Near-perfect matching exists
$>1$	Several vertices remain unmatched

Deficiency is closely related to Tutte’s theorem and the Gallai-Edmonds decomposition.

57.17 Perfect Matchings and Edge Covers

Suppose $G$ has no isolated vertices.

If $G$ possesses a perfect matching $M$ , then $M$ is also a minimum edge cover.

Indeed, every edge covers exactly two vertices, and every vertex must be covered. Since $M$ contains exactly

\frac{|V|}{2}

edges, no smaller edge cover is possible.

Thus perfect matchings simultaneously solve a covering problem and a pairing problem.

57.18 Perfect Matchings in Regular Graphs

Regular graphs frequently contain perfect matchings.

A $k$ -regular bipartite graph always has a perfect matching for every

k \geq 1.

This follows from Hall’s theorem.

Proof Sketch

Let

G=(X \cup Y,E)

be $k$ -regular.

For any subset

A \subseteq X,

there are exactly

k|A|

edges incident with vertices of $A$ .

All these edges end in

N(A).

Since every vertex in $N(A)$ has degree $k$ ,

k|A| \leq k|N(A)|.

Hence,

|A| \leq |N(A)|.

Hall’s condition holds, so a perfect matching exists.

This theorem is one of the most useful applications of Hall’s theorem.

57.19 Common Examples

Graph	Perfect Matching?
$P_n$	Yes iff $n$ even
$C_n$	Yes iff $n$ even
$K_n$	Yes iff $n$ even
$K_{m,n}$	Yes iff $m=n$
Odd cycle	No
Graph with isolated vertex	No

These examples illustrate that parity is important, but structure is equally important.

57.20 Exercises

Prove that every graph with a perfect matching has an even number of vertices.
Determine all perfect matchings of $C_6$ .
Show that $K_5$ has no perfect matching.
Prove that $K_{2n}$ has a perfect matching.
Determine whether the graph $P_8$ has a perfect matching.
Give an example of a graph with exactly one perfect matching.
Let $G$ be bipartite with parts $X$ and $Y$ . Prove that if $|X| \ne |Y|$ , then $G$ cannot have a perfect matching.
Prove that every perfect matching is maximum.
Show that every even cycle has exactly two perfect matchings.
Let $G$ be a graph with a perfect matching $M$ . Prove that every alternating cycle with respect to $M$ produces another perfect matching after flipping the edges.