Introduction to Graph Theory - Part 8

Suppose a company needs to assign jobs to applicants. Each applicant is qualified for certain positions, and each position can be filled by at most one person. How do we pair up as many applicants with jobs as possible? Or think of a dance: people want to be paired into couples, but not everyone is willing to dance with everyone else. How many couples can we form?

These are matching problems — and they are among the most elegant and practically important topics in graph theory. In this final part of our introduction, we'll define matchings formally, learn when perfect matchings exist, and see how a clever idea called augmenting paths ties everything together.

Matchings

Let's start with the basic setup. Given a graph, a matching is a set of edges that don't share any vertices — each vertex is "used" at most once.

Definition 40. A matching in a graph $G = (V, E)$ is a set of edges $M \subseteq E$ such that no two edges in $M$ share a vertex.

If a vertex $v$ is an endpoint of some edge in $M$, we say that $v$ is matched. Otherwise, $v$ is free (or unmatched).

Consider the graph $G = (\{1,2,3,4\}, \{(1,2), (2,3), (3,4), (1,4)\})$, a cycle $C_4$. The set $M = \{(1,2), (3,4)\}$ is a matching — the two edges don't share any vertex. The set $\{(1,2), (2,3)\}$ is not a matching, because vertex $2$ appears in both edges.

There are different notions of "best" for a matching, and it's important to distinguish them.

Definition 41. A matching $M$ is maximal if no edge can be added to $M$ without violating the matching property. In other words, every edge in $E \setminus M$ shares a vertex with some edge in $M$.

Definition 42. A matching $M$ is maximum if there is no matching with more edges. The size of a maximum matching is denoted $\nu(G)$.

A maximal matching is not necessarily maximum. In the path $P_4$ with vertices $1, 2, 3, 4$, the matching $\{(2,3)\}$ is maximal — we can't add $(1,2)$ or $(3,4)$ without conflicting with $(2,3)$ — but it's not maximum, since $\{(1,2), (3,4)\}$ has two edges.

The most desirable outcome is when every vertex gets matched.

Definition 43. A perfect matching is a matching that covers every vertex of the graph. That is, every vertex is matched.

A perfect matching can only exist when the number of vertices is even — after all, each edge in the matching accounts for exactly two vertices. But having an even number of vertices is necessary, not sufficient. The path $P_4$ has four vertices and admits a perfect matching $\{(1,2), (3,4)\}$, while the star $K_{1,3}$ also has four vertices but no perfect matching (the center vertex can be matched to only one of the three leaves, leaving two vertices free).

Observation 9. A perfect matching in a graph on $n$ vertices has exactly $\frac{n}{2}$ edges.

Augmenting Paths

How do we find a maximum matching? The key insight is a beautiful structural characterization discovered by Claude Berge in 1957. It revolves around the idea of augmenting paths.

Given a matching $M$, imagine walking through the graph along a path that alternates between edges not in $M$ and edges in $M$. If this path starts and ends at free vertices, we can "flip" every edge along the path — replacing the non-matching edges with matching edges and vice versa — to get a matching with one more edge.

Definition 44. Given a matching $M$, an alternating path is a path whose edges alternate between edges in $M$ and edges not in $M$.

Definition 45. An augmenting path (with respect to $M$) is an alternating path that starts and ends at free vertices.

Let's see this in action. Take the path $P_4$ with vertices $1, 2, 3, 4$ and matching $M = \{(2,3)\}$. The path $1, 2, 3, 4$ is an alternating path: the edge $(1,2)$ is not in $M$, the edge $(2,3)$ is in $M$, and the edge $(3,4)$ is not in $M$. Since vertices $1$ and $4$ are both free, this is an augmenting path. If we flip the edges, we get the new matching $M' = \{(1,2), (3,4)\}$ — one edge larger than $M$.

This idea leads to one of the most fundamental results in matching theory.

Theorem 10 (Berge, 1957). A matching $M$ is maximum if and only if there is no augmenting path with respect to $M$.

Proof. For the "only if" direction: suppose there exists an augmenting path $P$ with respect to $M$. The path has one more non-matching edge than matching edge (since both endpoints are free). Flipping all edges along $P$ produces a new matching $M'$ with $|M'| = |M| + 1$, so $M$ is not maximum.

For the "if" direction: suppose $M$ is not maximum, and let $M^*$ be a matching with $|M^*| > |M|$. Consider the symmetric difference $M \triangle M^* = (M \setminus M^*) \cup (M^* \setminus M)$ — the set of edges that belong to exactly one of the two matchings. Every vertex has at most one edge from $M$ and at most one edge from $M^*$, so in $M \triangle M^*$, every vertex has degree at most $2$. This means $M \triangle M^*$ is a union of isolated vertices, paths, and even cycles. The even cycles contribute equally to $M$ and $M^*$. Since $|M^*| > |M|$, there must be at least one path in $M \triangle M^*$ with more edges from $M^*$ than from $M$. This path starts and ends with edges from $M^*$, so its endpoints are free with respect to $M$ — it is an augmenting path.

Berge's theorem is not just a theoretical characterization — it directly leads to algorithms. To find a maximum matching, start with any matching (even the empty one) and repeatedly search for augmenting paths. Each augmenting path increases the matching by one edge, and by Berge's theorem, we stop exactly when the matching is maximum¹.

Hall's Marriage Theorem

Let's now focus on bipartite graphs, where matching theory is especially clean. Recall from Part 3 that a bipartite graph has two groups $A$ and $B$ with edges only between them. When does a bipartite graph have a matching that covers every vertex in $A$?

Think of it as a marriage problem: each person in group $A$ has a list of acceptable partners in group $B$. Can everyone in $A$ be matched? Philip Hall answered this question in 1935 with an elegant necessary and sufficient condition.

For a set $S \subseteq A$, we write $N(S)$ for the neighborhood of $S$ — the set of all vertices in $B$ that are adjacent to at least one vertex in $S$.

Theorem 11 (Hall, 1935). A bipartite graph $G = (A \cup B, E)$ has a matching that covers every vertex in $A$ if and only if $|N(S)| \geq |S|$ for every subset $S \subseteq A$.

The condition $|N(S)| \geq |S|$ is called Hall's condition. It says that every group of vertices in $A$ must collectively have at least as many neighbors in $B$ — otherwise, there simply aren't enough partners to go around.

The "only if" direction is straightforward: if every vertex in $S$ is matched, their partners are distinct vertices in $N(S)$, so $|N(S)| \geq |S|$. The "if" direction is more involved and can be proved using augmenting paths or by induction on $|A|$².

Let's check Hall's condition on a small example. Consider the bipartite graph with $A = \{1, 2, 3\}$, $B = \{a, b, c\}$, and edges $\{(1,a), (1,b), (2,a), (3,c)\}$. For $S = \{1\}$, we have $N(S) = \{a, b\}$, so $|N(S)| = 2 \geq 1$. For $S = \{2\}$, $N(S) = \{a\}$, so $|N(S)| = 1 \geq 1$. For $S = \{1, 2\}$, $N(S) = \{a, b\}$, so $|N(S)| = 2 \geq 2$. Checking all subsets confirms Hall's condition holds, and indeed a matching covering $A$ exists: $\{(1,b), (2,a), (3,c)\}$.

As a corollary, we can characterize when a bipartite graph has a perfect matching.

Corollary 2. A bipartite graph $G = (A \cup B, E)$ with $|A| = |B|$ has a perfect matching if and only if $|N(S)| \geq |S|$ for every subset $S \subseteq A$.

Vertex Covers and König's Theorem

There is a deep duality between matchings and a seemingly different concept: vertex covers.

Definition 46. A vertex cover of a graph $G = (V, E)$ is a set $C \subseteq V$ such that every edge in $E$ has at least one endpoint in $C$.

A matching picks edges so that no vertex is used twice. A vertex cover picks vertices so that no edge is missed. These two concepts are naturally opposed: every edge in a matching needs at least one of its endpoints in any vertex cover, so the size of any vertex cover is at least the size of any matching.

Observation 10. For any graph $G$, $\nu(G) \leq \tau(G)$, where $\nu(G)$ is the size of a maximum matching and $\tau(G)$ is the size of a minimum vertex cover.

In general graphs, this inequality can be strict. But in bipartite graphs, a remarkable theorem by Dénes König tells us that equality always holds.

Theorem 12 (König, 1931). In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover: $\nu(G) = \tau(G)$.

König's theorem is one of the jewels of combinatorics. It connects an optimization problem about selecting edges (matching) to one about selecting vertices (cover), and it tells us that in bipartite graphs, these dual problems always have the same answer. The proof can be constructed by starting with a maximum matching and carefully selecting one endpoint from each matched edge to form a minimum vertex cover³.

Beyond Bipartite Graphs

In bipartite graphs, Hall's theorem gives a clean condition for when a perfect matching exists. What about general graphs? The answer is given by a theorem of William Tutte.

For a graph $G$ and a set $S \subseteq V$, let $o(G - S)$ denote the number of connected components with an odd number of vertices in the graph obtained by removing $S$.

Theorem 13 (Tutte, 1947). A graph $G$ has a perfect matching if and only if $o(G - S) \leq |S|$ for every subset $S \subseteq V$.

Tutte's condition generalizes Hall's condition to non-bipartite graphs. The intuition is that each odd component needs at least one "escape edge" to a vertex in $S$ in order to match all its vertices, so there must be enough vertices in $S$ to accommodate all odd components.

We state Tutte's theorem here without proof, as the full argument is considerably more technical than Hall's theorem. It remains one of the deepest results in matching theory.

Wrapping Up the Series

With matchings, we've reached the end of this introduction to graph theory. Let's look back at the ground we've covered across all eight parts:

In Part 1, we saw how a puzzle about bridges gave birth to an entire field of mathematics. Part 2 laid the formal foundations with vertices, edges, and degrees. Part 3 introduced the main graph families — complete graphs, paths, cycles, bipartite graphs, trees, and regular graphs. Part 4 taught us how to move through graphs with walks, trails, and paths, and formalized Euler's bridge theorem. Part 5 took a deep dive into trees and their many equivalent characterizations. Part 6 added direction to our edges, opening up the world of digraphs, DAGs, and topological sorting. Part 7 explored graph coloring, from greedy algorithms to the Four Color Theorem. And here in Part 8, we studied matchings and the elegant duality between matchings and vertex covers.

These eight parts only scratch the surface. Graph theory is a vast and active field with connections to computer science, optimization, biology, and many other areas. If you've enjoyed this series, consider exploring some of the more advanced topics on this blog, such as Network Flows or Gallai's Path Conjecture, which build directly on the concepts we've developed here.