Maximal Matching

graph-theory

Definition

Maximal Matching

A matching $M$ is called maximal if there is no matching $M^{\prime }$ with $M⊊M^{\prime }$.

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

Examples

Matching

Maximal but not maximum

Consider the path graph with vertices $v_1,v_2,v_3,v_4$ and edges $\{v_1,v_2\}$, $\{v_2,v_3\}$, and $\{v_3,v_4\}$.

The matching $M=\{\{v_2,v_3\}\}$ is maximal, because no additional edge can be added without sharing an endpoint with $\{v_2,v_3\}$.

However, it is not maximum, because the matching $M^{\ast }=\{\{v_1,v_2\},\{v_3,v_4\}\}$ has larger size.