Matching

graph-theory

Definition

Matching

A matching of an undirected graph $G=(V,E)$ is a subset $M\subseteq E$ such that no two edges in $M$ share an endpoint.

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