matchings

A matchings in graph theory is a set of edges with the property that no two edges share a common endpoint. Equivalently, each vertex is incident to at most one edge of the set. A matching that covers every vertex is called a perfect matching, while a matching with the largest possible number of edges is called a maximum matching. In weighted graphs, one often seeks a maximum weight matching, where the sum of the edge weights is maximized.

Matchings are a fundamental object of study because they capture pairing structures in graphs. A central result is the augmenting path theorem: a matching is maximum if and only if there is no augmenting path with respect to that matching. In bipartite graphs, additional structure yields practical criteria and efficient algorithms, such as Hall’s theorem for existence of a perfect matching and König’s theorem, which states that the size of a maximum matching equals the size of a minimum vertex cover.

Algorithmic aspects distinguish bipartite and general graphs. For bipartite graphs, efficient algorithms exist to find maximum matchings, notably the Hopcroft–Karp algorithm with time complexity O(E sqrt(V)). Simpler approaches like Kuhn’s algorithm are slower in the worst case. For general graphs, the Edmonds blossom algorithm computes a maximum matching in polynomial time. For weighted cases, the Hungarian method solves the bipartite weighted matching problem, while generalized weighted matching in non-bipartite graphs relies on weighted extensions of the blossom framework.

Applications of matchings span assignment problems, scheduling, network design, and market mechanisms, including organ transplant allocations and other pairing problems. The study of matchings connects to broader topics such as vertex covers, transversals, and the broader theory of combinatorial optimization.