---
tag: 6A8X5JDRXM
kind: concept
name: Maximum-cardinality matching
aliases: [maximum-matching]
sources:
  - wikipedia: en:5989592@r1365861338
    locator: Maximum-cardinality matching
    note: adopted
    mention: wikipedia://en/5989592
    sections: [Summary]
same_as:
  wikidata: Q65088751
  wikipedia: Maximum-cardinality matching
inventory: [JK41H6TCMC]
---

## 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|0MJ04A50QW]] is a subgraph where no two edges share a vertex. The [[cardinality|0G0ASKNA6Z]] 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|05ZPH8KF9K]]. 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.