Nobody has pulled this card yet. The first copy makes you its discoverer.
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.