From: Fred Galvin <galvin@math.ukans.edu>
Subject: Re: Stable marriages problem - looking for a proof
Date: Thu, 5 Aug 1999 11:57:11 -0500
Newsgroups: sci.math
Keywords: references

On 5 Aug 1999, Remco Gerlich wrote:

> For a lab session, I have to implement a program that finds a solution
> for "the stable marriages problem". I'm thinking of using a simple
> generate-and-test approach, but the text mentions that "this is always
> possible, by a theorem from graph theory."
> 
> I'd like to see the theorem and the proof, since it may suggest
> a more efficient approach for my program.
> 
> The stable marriages problem: given a group of n males and n females,
> where each has a list of preferences for the members of the opposite
> sex. Make n male-female couples that marry, where each marriage is
> stable. A marriage is unstable if there is a couple in the group that
> isn't married, and that has each other higher on their preferences
> list than their spouses.
> 
> Does anyone know which theorem from graph theory proves that
> this is always possible, and if the proof is online somewhere?
> Or a well-known book that has it?

D. Gale and L. S. Shapley, College admissions and the stability of
marriage, American Mathematical Monthly 69 (1962), 9-15.

Dan Gusfield and Robert W. Irving, _The Stable Marriage Problem:
Structures and Algorithms_, MIT Press, 1989.

Donald E. Knuth, _Stable Marriage and Its Relation to Other Combinatorial
Problems_, American Mathematical Society, 1997.

Douglas B. West, _Introduction to Graph Theory_, Prentice-Hall, 1996.
(Section 3.2, under "Stable Matchings")