= 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.
Back to article page
