Matching

Definition

Let $G$ be a graph. A matching in $G$ is a set $M$ of edges of $G$ such that no two distinct edges of $M$ have a common end.

Remarks

A vertex is matched if it is an end of an edge of $M$. Otherwise it is unmatched. A maximal matching is not contained in a larger matching. A maximum matching has the largest number of edges, the matching number $\nu(G)$. Every maximum matching is maximal, but the converse is false: in the path graph $P_4$, the middle edge alone is a maximal matching.

Explanations

L1 human

A matching pairs some vertices along edges, and no vertex is in two pairs. For example, it can pair workers with jobs that they can do, one job per worker.