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.
Articles by others on the same topic
The Gale-Shapley algorithm, also known as the deferred acceptance algorithm, is a method for solving the stable marriage problem, which was first proposed by David Gale and Lloyd Shapley in their 1962 paper. The algorithm aims to find a stable matching between two equally sized sets—typically referred to as "men" and "women"—based on their preferences for each other.