 Stable matching in a bipartite graph

Give each vertex a strict ordering of its neighbours of a vertex, all preferred to being unmatched. A matching in a graph is stable if no unused edge has both endpoints preferring each other to their current partners, with an unmatched endpoint willing to accept any neighbour. The Gale-Shapley algorithm produces a stable matching even when the two parts have unequal sizes and some pairs are unacceptable.