= Gale-Shapley algorithm
{c}
An unmatched vertex in the proposing part proposes to its best untried neighbour. The receiving vertex keeps its preferred proposal, rejecting any other. There are at most as many proposals as <edges>, so this terminates. A rejected proposer can never become preferable to the receiver's final partner, since the receiver's held partner only improves. An edge never proposed along cannot block either: its proposer finishes with a better partner or has exhausted all choices. Thus the final <matching in a graph> is stable.
Back to article page
