Greedy matching

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.