Matching

Given an Undirected Graph $G=(V,E)$ a matching is a subset of edges $M\subseteq E$ such that for all vertices $v\in V$, at most one edge of $M$ is incident on $v$.

We say that a vertex $v\in V$ is matched by the matching $M$ if some edge in $M$ is incident on $v$ otherwise, $v$ is unmatched.