Maximum cardinality matching is a concept in graph theory referring to a matching (a set of edges without common vertices) that includes the maximum number of edges possible. In a simple undirected graph, a matching pairs up vertices such that no two edges share a vertex. ### Key Points: 1. **Matching**: A matching in a graph is a set of edges where no two edges share a vertex.
Articles by others on the same topic
A maximum cardinality matching is a matching in a graph with as many edges as any matching in a graph of the same graph. It has cardinality , the matching number, and need not be unique or be a perfect matching. For example, any single edge of a triangle in a graph is a maximum cardinality matching, but leaves one vertex unmatched. Berge's theorem characterizes these optima by the absence of an augmenting path in a matching.