Maximum Matching

graph-theory

Definition

Maximum Matching

A matching $M$ is called maximum if there is for each other matching $M^{\prime }\ne M$ it holds that $|M|\ge |M^{\prime }|$.

Example: The highlighted edge sets below show a matching $M_1$, a maximal matching $M_2$, and a maximum matching $M_3$.