Matchings and Coverings

Augmenting paths, Berge's theorem, Hall's marriage theorem, König's theorem, stable matchings via the Gale--Shapley algorithm, and weighted matchings --- all with complete proofs.

Folio Official

March 1, 2026

1. Basic Concepts

Definition 1 (Matching).

A matching in a graph

G = (V, E)

is a set

M \subseteq E

of pairwise non-adjacent edges (no two edges in

M

share an endpoint). A vertex incident to an edge of

M

is said to be matched (or saturated). A matching of maximum cardinality is called a maximum matching. A matching that saturates every vertex of

G

is a perfect matching.

In the following bipartite graph, the thick edges form a matching $M = {{x_{1}, y_{2}}, {x_{2}, y_{3}}}$ of size $2$ . The vertex $x_{3}$ is unmatched:

Definition 2 (Augmenting path).

An alternating path with respect to a matching

M

is a path whose edges alternate between

M

and

E ∖ M

. An alternating path whose two endpoints are both unsaturated by

M

is called an augmenting path.

In the graph above, the path $x_{3} - y_{1} - x_{1} - y_{2} - x_{2} - y_{3}$ is not augmenting because $y_{3}$ is matched. However, the path $x_{3} - y_{1}$ is an augmenting path (both $x_{3}$ and $y_{1}$ are unmatched). Flipping along it yields the larger matching ${{x_{3}, y_{1}}, {x_{1}, y_{2}}, {x_{2}, y_{3}}}$ :

2. Berge's Theorem

Theorem 3 (Berge's theorem).

A matching

M

is a maximum matching if and only if there is no augmenting path with respect to

M

Proof.

(\Rightarrow)

: If an augmenting path

P

exists, the symmetric difference

M^{'} = M \oplus E (P)

(exchanging matched and unmatched edges along

P

) is a matching with

∣ M^{'} ∣ = ∣ M ∣ + 1

, contradicting the maximality of

M

(\Leftarrow)

: Suppose

M

is not maximum, and let

M^{*}

be a maximum matching with

∣ M^{*} ∣ > ∣ M ∣

. Consider

H = M \oplus M^{*}

. Every vertex of

H

has degree at most

2

(at most one edge from

M

and one from

M^{*}

), so each connected component of

H

is a path or an even-length cycle. Since

∣ M^{*} ∣ > ∣ M ∣

, some component has more edges from

M^{*}

than from

M

. A cycle has equally many edges from each, so this component must be a path. It begins and ends with edges of

M^{*}

, meaning both endpoints are unsaturated by

M

. This path is therefore an augmenting path for

M

. □

3. Matchings in Bipartite Graphs

Definition 4 (Bipartite graph).

A graph

G = (V, E)

is bipartite if

V

can be partitioned as

V = X ⊔ Y

so that every edge joins a vertex in

X

to a vertex in

Y

The following bipartite graph satisfies Hall's condition ( $∣ N (S) ∣ \geq ∣ S ∣$ for every $S \subseteq X$ ) and therefore admits a perfect matching of $X$ :

Theorem 5 (Hall's marriage theorem).

A bipartite graph

G = (X ⊔ Y, E)

has a matching that saturates every vertex of

X

if and only if

∣ N (S) ∣ \geq ∣ S ∣

for every

S \subseteq X

, where

N (S)

denotes the neighborhood of

S

Proof.

(\Rightarrow)

: If a matching

M

saturates

X

, then for any

S \subseteq X

, the matching pairs the vertices of

S

with

∣ S ∣

distinct vertices in

Y

, so

∣ N (S) ∣ \geq ∣ S ∣

(\Leftarrow)

: We prove the contrapositive. Suppose no matching saturates

X

. Let

M

be a maximum matching with

∣ M ∣ < ∣ X ∣

. Pick an unsaturated vertex

u \in X

. Let

Z

be the set of all vertices reachable from

u

via alternating paths. Set

S = Z \cap X

and

T = Z \cap Y

. Since

u \in S

and

u

is unsaturated,

u

contributes to

S

. Since there is no augmenting path (Berge's theorem), every vertex in

T

is matched by

M

, and its partner under

M

lies in

S

(being reachable via the alternating path). Thus

∣ T ∣ = ∣ S ∣ - 1

. Moreover,

N (S) \subseteq T

: if some neighbor

y

S

lay outside

T

, then

y

would be reachable from

u

via an alternating path, placing

y

Z \cap Y = T

, a contradiction. Therefore

∣ N (S) ∣ \leq ∣ T ∣ = ∣ S ∣ - 1 < ∣ S ∣

. □

4. König's Theorem

Definition 6 (Vertex cover).

A vertex cover of

G = (V, E)

is a set

C \subseteq V

such that every edge has at least one endpoint in

C

Theorem 7 (König's theorem).

In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Proof.

For any matching

M

and vertex cover

C

, we have

∣ C ∣ \geq ∣ M ∣

(each edge of

M

requires at least one vertex of

C

to cover it). We show equality is attained. Take a maximum matching

M

and construct the reachability set

Z

as in the proof of Hall's theorem. Define

C = (X ∖ Z) \cup (Y \cap Z)

. One verifies that

∣ C ∣ = ∣ M ∣

and that

C

is a vertex cover. □

5. Stable Matchings

Definition 8 (Stable matching).

Let

M

be a set of

n

men and

W

a set of

n

women, each with a strict preference ordering over the opposite set. A perfect matching

μ

is unstable if there exist a man

m

and a woman

w

, not paired with each other, such that

m

prefers

w

μ (m)

and

w

prefers

m

μ (w)

. A matching with no such pair is called a stable matching.

Theorem 9 (Gale–Shapley).

The Gale–Shapley algorithm (men-proposing version) terminates in finitely many steps and outputs a stable matching. Moreover, the matching it produces is men-optimal: every man is matched with the best partner he could have in any stable matching.

Proof.

Termination. Each man proposes to each woman at most once, so the algorithm terminates after at most

n^{2}

proposals.

Stability. Suppose an unstable pair

(m, w)

exists. Either

m

never proposed to

w

, or he did and was rejected. In the first case,

m

prefers

μ (m)

w

(since men propose in order of preference), contradicting the assumption that

(m, w)

is unstable. In the second case,

w

was holding a proposal she preferred to

m

at the time; since a woman's partner can only improve over the course of the algorithm,

w

prefers

μ (w)

m

in the final matching — again a contradiction.

Men-optimality is established by inductively showing that no man is ever rejected by a woman who could be his partner in some stable matching. □

6. Weighted Matchings

Remark 10.

When each edge

e

carries a weight

w (e)

, a matching

M

maximizing

\sum_{e \in M} w (e)

is called a maximum-weight matching. For bipartite graphs, the Hungarian method (Kuhn–Munkres algorithm) finds a maximum-weight matching in

O (n^{3})

time. This method is based on LP duality and can be seen as a weighted generalization of Kö

O (n^{3})

running time.

Graph Theory Discrete Mathematics Textbook Matchings Hall's Theorem König's Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Matchings and Coverings

Augmenting paths, Berge's theorem, Hall's marriage theorem, König's theorem, stable matchings via the Gale--Shapley algorithm, and weighted matchings --- all with complete proofs.

Folio Official

March 1, 2026

1. Basic Concepts

Definition 1 (Matching).

A matching in a graph

G = (V, E)

is a set

M \subseteq E

of pairwise non-adjacent edges (no two edges in

M

share an endpoint). A vertex incident to an edge of

M

is said to be matched (or saturated). A matching of maximum cardinality is called a maximum matching. A matching that saturates every vertex of

G

is a perfect matching.

In the following bipartite graph, the thick edges form a matching $M = {{x_{1}, y_{2}}, {x_{2}, y_{3}}}$ of size $2$ . The vertex $x_{3}$ is unmatched:

Definition 2 (Augmenting path).

An alternating path with respect to a matching

M

is a path whose edges alternate between

M

and

E ∖ M

. An alternating path whose two endpoints are both unsaturated by

M

is called an augmenting path.

2. Berge's Theorem

Theorem 3 (Berge's theorem).

A matching

M

is a maximum matching if and only if there is no augmenting path with respect to

M

Proof.

(\Rightarrow)

: If an augmenting path

P

exists, the symmetric difference

M^{'} = M \oplus E (P)

(exchanging matched and unmatched edges along

P

) is a matching with

∣ M^{'} ∣ = ∣ M ∣ + 1

, contradicting the maximality of

M

(\Leftarrow)

: Suppose

M

is not maximum, and let

M^{*}

be a maximum matching with

∣ M^{*} ∣ > ∣ M ∣

. Consider

H = M \oplus M^{*}

. Every vertex of

H

has degree at most

2

(at most one edge from

M

and one from

M^{*}

), so each connected component of

H

is a path or an even-length cycle. Since

∣ M^{*} ∣ > ∣ M ∣

, some component has more edges from

M^{*}

than from

M

. A cycle has equally many edges from each, so this component must be a path. It begins and ends with edges of

M^{*}

, meaning both endpoints are unsaturated by

M

. This path is therefore an augmenting path for

M

. □

3. Matchings in Bipartite Graphs

Definition 4 (Bipartite graph).

A graph

G = (V, E)

is bipartite if

V

can be partitioned as

V = X ⊔ Y

so that every edge joins a vertex in

X

to a vertex in

Y

The following bipartite graph satisfies Hall's condition ( $∣ N (S) ∣ \geq ∣ S ∣$ for every $S \subseteq X$ ) and therefore admits a perfect matching of $X$ :

Theorem 5 (Hall's marriage theorem).

A bipartite graph

G = (X ⊔ Y, E)

has a matching that saturates every vertex of

X

if and only if

∣ N (S) ∣ \geq ∣ S ∣

for every

S \subseteq X

, where

N (S)

denotes the neighborhood of

S

Proof.

(\Rightarrow)

: If a matching

M

saturates

X

, then for any

S \subseteq X

, the matching pairs the vertices of

S

with

∣ S ∣

distinct vertices in

Y

, so

∣ N (S) ∣ \geq ∣ S ∣

(\Leftarrow)

: We prove the contrapositive. Suppose no matching saturates

X

. Let

M

be a maximum matching with

∣ M ∣ < ∣ X ∣

. Pick an unsaturated vertex

u \in X

. Let

Z

be the set of all vertices reachable from

u

via alternating paths. Set

S = Z \cap X

and

T = Z \cap Y

. Since

u \in S

and

u

is unsaturated,

u

contributes to

S

. Since there is no augmenting path (Berge's theorem), every vertex in

T

is matched by

M

, and its partner under

M

lies in

S

(being reachable via the alternating path). Thus

∣ T ∣ = ∣ S ∣ - 1

. Moreover,

N (S) \subseteq T

: if some neighbor

y

S

lay outside

T

, then

y

would be reachable from

u

via an alternating path, placing

y

Z \cap Y = T

, a contradiction. Therefore

∣ N (S) ∣ \leq ∣ T ∣ = ∣ S ∣ - 1 < ∣ S ∣

. □

4. König's Theorem

Definition 6 (Vertex cover).

A vertex cover of

G = (V, E)

is a set

C \subseteq V

such that every edge has at least one endpoint in

C

Theorem 7 (König's theorem).

In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Proof.

For any matching

M

and vertex cover

C

, we have

∣ C ∣ \geq ∣ M ∣

(each edge of

M

requires at least one vertex of

C

to cover it). We show equality is attained. Take a maximum matching

M

and construct the reachability set

Z

as in the proof of Hall's theorem. Define

C = (X ∖ Z) \cup (Y \cap Z)

. One verifies that

∣ C ∣ = ∣ M ∣

and that

C

is a vertex cover. □

5. Stable Matchings

Definition 8 (Stable matching).

Let

M

be a set of

n

men and

W

a set of

n

women, each with a strict preference ordering over the opposite set. A perfect matching

μ

is unstable if there exist a man

m

and a woman

w

, not paired with each other, such that

m

prefers

w

μ (m)

and

w

prefers

m

μ (w)

. A matching with no such pair is called a stable matching.

Theorem 9 (Gale–Shapley).

Proof.

Termination. Each man proposes to each woman at most once, so the algorithm terminates after at most

n^{2}

proposals.

Stability. Suppose an unstable pair

(m, w)

exists. Either

m

never proposed to

w

, or he did and was rejected. In the first case,

m

prefers

μ (m)

w

(since men propose in order of preference), contradicting the assumption that

(m, w)

is unstable. In the second case,

w

was holding a proposal she preferred to

m

at the time; since a woman's partner can only improve over the course of the algorithm,

w

prefers

μ (w)

m

in the final matching — again a contradiction.

Men-optimality is established by inductively showing that no man is ever rejected by a woman who could be his partner in some stable matching. □

6. Weighted Matchings

Remark 10.

When each edge

e

carries a weight

w (e)

, a matching

M

maximizing

\sum_{e \in M} w (e)

is called a maximum-weight matching. For bipartite graphs, the Hungarian method (Kuhn–Munkres algorithm) finds a maximum-weight matching in

O (n^{3})

time. This method is based on LP duality and can be seen as a weighted generalization of Kö

O (n^{3})

running time.

Graph Theory Discrete Mathematics Textbook Matchings Hall's Theorem König's Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Matchings and Coverings

1. Basic Concepts

2. Berge's Theorem

3. Matchings in Bipartite Graphs

4. König's Theorem

5. Stable Matchings

6. Weighted Matchings

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

Matchings and Coverings

1. Basic Concepts

2. Berge's Theorem

3. Matchings in Bipartite Graphs

4. König's Theorem

5. Stable Matchings

6. Weighted Matchings

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences