Mathematics.

graph algorithms

Matching Theory

Graph Theory30 minDifficulty5 out of 10

You should know: bipartite graphs

Overview

A matching in a graph is a set of edges with no two sharing a vertex — every vertex touches at most one matching edge. A maximum matching has the largest possible number of edges, and a perfect matching covers every vertex. For bipartite graphs, Hall's marriage theorem gives a clean existence criterion for a perfect matching: one exists (saturating one side) if and only if every subset S of that side has at least |S| neighbors on the other side (the 'marriage condition'). The Hungarian algorithm finds a maximum matching (or minimum-cost perfect matching) in bipartite graphs in polynomial time, and matching problems reduce directly to network flow problems, connecting the two areas.

Intuition

Picture pairing up dance partners at a formal, where each person can dance with at most one partner at a time — a matching is exactly such a set of non-overlapping pairs. Hall's marriage theorem formalizes when a full pairing is possible: if any group of k people on one side collectively knows fewer than k people on the other side, that group can never all be matched — a bottleneck. This exact logic underlies assigning residents to hospitals, workers to shifts, and kidney donors to recipients.

Formal Definition

Definition

For a graph G = (V, E), a matching M ⊆ E has no shared endpoints:

M⊆E, ∀e1,e2∈M, e1≠e2⇒e1∩e2=∅M \subseteq E,\ \forall e_1, e_2 \in M,\ e_1 \ne e_2 \Rightarrow e_1 \cap e_2 = \emptyset
Matching definition
Perfect matching: every v∈V is an endpoint of exactly one edge in M\text{Perfect matching: every } v \in V \text{ is an endpoint of exactly one edge in } M
Perfect matching
Hall’s theorem: bipartite G=(X∪Y,E) has a matching saturating X  ⟺  ∀S⊆X, ∣N(S)∣≥∣S∣\text{Hall's theorem: bipartite } G=(X \cup Y, E) \text{ has a matching saturating } X \iff \forall S \subseteq X,\ |N(S)| \ge |S|
Hall's marriage theorem

Worked Examples

  1. Try matching 1-a: this uses vertex 1 and vertex a. Vertex 2 can then only match with b (since a is taken), via edge 2-b.

    M={1-a, 2-b}M = \{1\text{-}a,\ 2\text{-}b\}

  2. Both vertices in X (1 and 2) and both in Y (a and b) are covered, with no shared endpoints between the two edges. This is a perfect matching of size 2.

    ∣M∣=2|M| = 2

Answer: Maximum matching = {1-a, 2-b}, size 2 (a perfect matching).

Practice Problems

Difficulty 3/10

A matching in a graph has 4 edges. How many vertices does it cover (assuming no two edges share an endpoint, by definition of matching)?

Difficulty 5/10

A medical residency matching program pairs 100 graduating students with 100 hospital residency slots (one student per slot). If Hall's condition holds for every subset of students, what does that guarantee?

Difficulty 5/10

Explain how finding a maximum bipartite matching can be reduced to a maximum flow problem.

Quiz

A matching in a graph is a set of edges such that:
Hall's marriage theorem gives a condition for a bipartite matching saturating side X to exist. That condition is:
Maximum bipartite matching can be computed by reducing it to:

Summary

  • A matching pairs up vertices via edges with no shared endpoints; a perfect matching covers every vertex.
  • Hall's marriage theorem gives an exact existence criterion for bipartite matchings via the 'every subset has enough neighbors' condition.
  • Maximum bipartite matching reduces to a unit-capacity max-flow problem, linking matching theory directly to network flow algorithms.

References

  1. WebsiteWikipedia — Matching (graph theory)