Maximum-cardinality matching

In graph theory, a maximum-cardinality matching is a special kind of subgraph useful in many computational contexts. Given a graphG, a matching is a subgraph where no two edges share a vertex. The cardinality of the matching is the number of edges in the subgraph, and the maximum cardinality is the largest number of edges a matching can contain. A matching for a given graph is a maximum-cardinality matching if its cardinality is this maximum cardinality. If we think of each edge as "covering" the vertices it connects exactly once, then a maximal matching is also the largest non-overlapping cover of the graph. If all the vertices are covered, we call it a perfect matching. For finite graphs, a maximum-cardinality matching always exists, but is not usually unique. The cardinality of the matching is never more than half the number of vertices and also never more than the number of edges.

An important special case of the maximum-cardinality matching problem is when G is a bipartite graph representing a binary relation, whose vertices V are partitioned between left vertices in X and right vertices in Y, and edges in E always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case.

The calculation of a maximum matching for a given graph is a fundamental task in computational graph theory. There are nonconstructive characterization theorems for the size of a maximum matching. This article is about computation of maximum matchings.