matching

Let $G$ be a graph. A matching $M$ on $G$ is a subset of the edges of $G$ such that each vertex in $G$ is incident with no more than one edge in $M$.

It is easy to find a matching on a graph; for example, the empty set will always be a matching. Typically, the most interesting matchings are maximal matchings. A maximal matching on a graph $G$ is simply a matching of the largest possible size.

A perfect matching is a matching that saturates every vertex.