A <maximal matching> is a <matching in a graph> to which no extra <edge> can be added while retaining all current selected <edges>. Equivalently, no <edge> joins two <unmatched vertices in a matching>; those <vertices> form an <independent set>. Every <maximum cardinality matching> is a <maximal matching>, but the converse fails.

Take the <path graph> $P_4$ with <vertices> $1,2,3,4$ and <edges> $(1,2),(2,3),(3,4)$. A <greedy algorithm> that first selects the middle <edge> produces $M=\{(2,3)\}$. Both remaining <edges> touch a matched <vertex>, so this size-one <matching in a graph> is maximal. Yet $N=\{(1,2),(3,4)\}$ has two <edges>. No <matching in a graph> on four <vertices> has more than two <edges>, so $N$ is a <maximum cardinality matching>. The two remaining free <vertices> of $M$, namely $1$ and $4$, are not adjacent; that does not prevent a longer <augmenting path in a matching> from joining them.

\Image[/matching-greedy-middle-edge-trap.png]
{title=Choosing the middle <edge> of P₄ gives a <maximal matching> of size one; the outer <edges> give a <maximum cardinality matching> of size two}

Maximality is useful as a quick stopping rule and a modest guarantee. For any <maximal matching> $M$ and <maximum cardinality matching> $N$ in a finite <simple graph>, every <edge> of $N$ touches an endpoint of an <edge> of $M$. Assign it to one such <edge> of $M$. Since $N$ has disjoint endpoints, each <edge> of $M$ receives at most two assignments, proving $|N|\leq2|M|$. The P₄ example reaches equality. Thus maximality guarantees at least half the largest <cardinality>, but says nothing comparable about arbitrary edge benefits. Its selected endpoints also form a <vertex cover>, as explained under <vertex cover>.


 Maximal matching (source code)