What is the difference between a matching and a perfect matching?

A matching is any set of edges with no shared vertices — some vertices may be left unmatched. A perfect matching is a special matching that covers every single vertex in the graph. Every perfect matching is a matching, but not every matching is perfect.

Perfect Matching — Definition, Formula & Examples

A perfect matching is a set of edges in a graph such that every vertex is included in exactly one edge. In other words, every vertex is paired with exactly one neighbor, with no vertex left unmatched.

Given a graph $G = (V, E)$ , a perfect matching $M \subseteq E$ is a set of pairwise non-adjacent edges (no two edges share a vertex) such that every vertex $v \in V$ is an endpoint of exactly one edge in $M$ . A necessary condition is that $|V|$ is even. For bipartite graphs, Hall's marriage theorem gives a necessary and sufficient condition for the existence of a perfect matching.

Key Formula

|M| = \frac{|V|}{2}

Where:

$M$ = The perfect matching — the set of selected edges
$|V|$ = The total number of vertices in the graph (must be even)

How It Works

To find a perfect matching, you need to select edges so that each vertex appears in exactly one selected edge. Start by checking whether the graph has an even number of vertices — if it does not, no perfect matching can exist. For bipartite graphs

G = (A \cup B, E)

with

|A| = |B|

, Hall's theorem states a perfect matching exists if and only if for every subset

S \subseteq A

, the neighborhood

N(S)

satisfies

|N(S)| \geq |S|

. Algorithms such as the Hopcroft–Karp algorithm efficiently find perfect matchings in bipartite graphs, while Edmonds' blossom algorithm handles general graphs.

Worked Example

Problem: Determine whether the complete bipartite graph

K_{3,3}

(with vertex sets

A = \{a_1, a_2, a_3\}

and

B = \{b_1, b_2, b_3\}

) has a perfect matching, and if so, find one.

Step 1: Check that the total number of vertices is even.

|V| = |A| + |B| = 3 + 3 = 6 \text{ (even, so a perfect matching is possible)}

Step 2: Verify Hall's condition. In

K_{3,3}

, every vertex in

A

is adjacent to all three vertices in

B

, so for any subset

S \subseteq A

, the neighborhood

N(S) = B

whenever

S \neq \emptyset

. Thus

|N(S)| = 3 \geq |S|

for all

S

|N(S)| = 3 \geq |S| \quad \text{for all } S \subseteq A

Step 3: Construct a perfect matching by pairing each vertex in

A

with a distinct vertex in

B

M = \{(a_1, b_1),\; (a_2, b_2),\; (a_3, b_3)\}

Step 4: Confirm:

|M| = 3 = |V|/2 = 6/2

, every vertex appears exactly once, and no two edges share a vertex.

|M| = 3 = \frac{6}{2} \checkmark

Answer: Yes,

K_{3,3}

has a perfect matching. One example is

M = \{(a_1, b_1), (a_2, b_2), (a_3, b_3)\}

Another Example

Problem: Does the cycle graph

C_5

(a 5-vertex cycle) have a perfect matching?

Step 1: Count the vertices in

C_5

|V| = 5 \text{ (odd)}

Step 2: A perfect matching requires

|M| = |V|/2

, which must be an integer. Since

5/2 = 2.5

, this is impossible.

\frac{|V|}{2} = \frac{5}{2} \notin \mathbb{Z}

Answer: No.

C_5

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

Why It Matters

Perfect matchings appear throughout combinatorics courses and algorithms classes when studying assignment problems, scheduling, and network flows. In operations research, assigning workers to tasks at minimum cost reduces to finding a minimum-weight perfect matching. They also underpin results in chemistry (Kekulé structures of molecules) and computer science (stable marriage algorithms).

Common Mistakes

Mistake: Forgetting that the graph must have an even number of vertices for a perfect matching to exist.

Correction: Always check

|V|

first. If

|V|

is odd, you can immediately conclude no perfect matching exists.

Mistake: Confusing a maximum matching with a perfect matching.

Correction: A maximum matching is the largest matching possible in the graph, but it may still leave some vertices unmatched. A perfect matching leaves zero vertices unmatched. A perfect matching is maximum, but a maximum matching is not necessarily perfect.

Related Terms

Graph — The underlying structure where matchings are found
Bipartite Graph — Graph type where Hall's theorem applies
Edge — A perfect matching is a specific set of edges
Vertex — Every vertex must be covered exactly once
Combinatorics — Broader field that studies matchings and counting