Maximal matching

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.

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|\le 2|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.

A greedy matching starts with the empty matching in a graph, scans all edges in some order, and selects an edge exactly when both endpoints are unmatched vertices in a matching. For a finite graph, a complete scan returns a maximal matching: a rejected edge had a matched endpoint, which stays matched thereafter. Stopping before all edges have been considered need not give maximality. Changing the order can change the result; on P₄, middle-first gives one pair, whereas outer-first gives two. A greedy algorithm of this form never revisits its choices, while an augmenting path in a matching does.