Maximum-cardinality matching

Summary

In graph theory, a maximum-cardinality matching is a special kind of subgraph useful in many computational contexts. Given a graph $G$, 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.