Matchings and Covers

A matching in a graph selects edges with no shared endpoints. The theory of matchings connects combinatorial optimization, linear programming, and polyhedral geometry, with applications from scheduling to chemistry.

Basic Definitions

Definition6.1Matching, Maximum Matching, Perfect Matching

A matching $M$ in $G$ is a set of pairwise non-adjacent edges. A vertex is saturated by $M$ if it is an endpoint of some edge in $M$ . The matching number $\nu(G)$ is the maximum size of a matching. A perfect matching saturates all vertices (requires $|V|$ even). A matching is maximal if no edge can be added; maximal $\neq$ maximum in general.

Definition6.2Vertex Cover and König's Duality

A vertex cover $S$ is a set of vertices such that every edge has at least one endpoint in $S$ . The vertex cover number $\tau(G) = \min|S|$ . Always $\nu(G) \leq \tau(G)$ (each matching edge needs a distinct cover vertex). König's theorem (bipartite): $\nu(G) = \tau(G)$ when $G$ is bipartite. For general graphs, the Gallai theorem: $\nu(G) + \tau(G) = |V(G)|$ when every component has a perfect matching... no, correctly: $\alpha(G) + \tau(G) = |V|$ where $\alpha$ is the independence number.

Augmenting Paths

ExampleAugmenting Path Algorithm

An augmenting path for matching $M$ is a path that starts and ends at unsaturated vertices and alternates between edges not in $M$ and edges in $M$ . Berge's lemma: $M$ is maximum if and only if no augmenting path exists. To enlarge $M$ : find an augmenting path $P$ and set $M' = M \triangle P$ (symmetric difference). This increases $|M|$ by 1. The Hopcroft-Karp algorithm finds maximum matchings in bipartite graphs in $O(\sqrt{n} \cdot m)$ time.

RemarkEdmonds' Blossom Algorithm

For general (non-bipartite) graphs, augmenting paths can be found using Edmonds' blossom algorithm. A blossom is an odd cycle where all but one vertex is matched within the cycle. The algorithm "shrinks" blossoms to single vertices, finds augmenting paths in the contracted graph, and "expands" back. This runs in $O(n^2 m)$ time (improved to $O(n^{1/2}m)$ with Micali-Vazirani).