Maximum-cardinality matching

A matching containing the greatest possible number of edges in a graph. It pairs as many vertices as possible without allowing any vertex to belong to more than one edge.

Matching (graph theory): A set of graph edges that share no endpoints. A maximum-cardinality matching is a matching chosen to maximize the number of its edges.
Graph (discrete mathematics): A structure consisting of vertices connected by edges. Matchings select edges from this underlying structure.
Maximum-weight matching: A matching maximizing the sum of its edge weights. It values edge weights, so it need not contain the most edges.
Assignment problem: An optimization problem assigning distinct agents to distinct tasks under specified costs or constraints. A bipartite maximum matching tests how many agents can receive compatible tasks.
Augmenting path: A path whose edges alternate between outside and inside a matching, beginning and ending at unmatched vertices. Flipping membership along this path increases matching size by one.
Vertex cover: A set of vertices that includes at least one endpoint of every edge. Every matching has size at most every vertex cover's size.
Maximal matching: A matching to which no edge can be added while preserving the matching property. Being maximal does not guarantee having the greatest possible cardinality.
Marriage theorem: Hall's theorem characterizes when a bipartite graph has a matching covering one side. It determines whether every member of one group can be assigned a distinct partner.
Berge's lemma: A matching is maximum exactly when no augmenting path exists. It gives the central optimality test for maximum-cardinality matchings.
Independent set (graph theory): A set of vertices with no edges between any pair. Unmatched vertices in a maximum matching form a useful target in related optimization questions.

Linked from 13 pages