Matchings & Hall's Theorem

We dive deep into matchings — sets of pairwise non-adjacent edges. The key algorithmic idea is augmenting paths: if one exists, the matching isn't maximum. Hall's theorem characterizes when a bipartite graph has a perfect matching. Frobenius' theorem extends this to general matchings.

Learning Objectives

Define matchings, perfect matchings, and maximum matchings

Understand augmenting paths and use them to improve matchings

State and apply Hall's theorem (marriage theorem)

State Frobenius' deficiency formula

Key Concepts

Matchings & Augmenting Paths

A matching $M$ in a graph is a set of edges with no shared endpoints. A perfect matching covers all vertices. A matching is maximum if no larger matching exists.

An augmenting path for matching $M$ is a path that alternates between non-matching and matching edges, with both endpoints unmatched. If an augmenting path exists, we can increase the matching size by 1.

-
If an augmenting path exists, flip it to get a larger matching
-
No augmenting path means the matching is maximum
-
Augmenting path algorithm: find augmenting paths until none exist
-
The algorithm also produces a minimum vertex cover: $T \cup (A \setminus S)$

Hall's Theorem

Hall's theorem (Marriage Theorem) gives a necessary and sufficient condition for a bipartite graph to have a matching that covers one side completely.

Let $G = (A \cup B, E)$ be bipartite. For $S \subseteq A$ , let $N(S)$ denote the set of neighbors of $S$ in $B$ .

-
Hall's condition: every subset $S$ of one side has at least $|S|$ neighbors on the other side
-
To disprove: find one set $S$ where $|N(S)| < |S|$
-
Perfect matching in bipartite: Hall's condition must hold for both sides
-
Deficiency: $\max_S(|S| - |N(S)|)$ measures how far we are from a perfect matching

W7: Covers, Independent Sets & Kruskal W9: Edge Coloring, König & Max Flow