The authors introduce the Stable Matching Problem. They explain a more complicated instance of the SMP first, involving companies with many slots seeking interns. This is to illustrate the potential real-life usefulness of a solution to the problem, I guess.

Then, they go do their “getting to the mathematically clean core” thing which they described in the preface, and abandon the companies with many slots thing, and simplify the problem to stable matchings of n men with n women. They clearly define their terms “matching” and “perfect matching” and “instability” and “stable matching,” with respect to this example. Then they set up an example case, and show it's possible to have two stable matchings for a given set of preferences.

Then, they present the Gale-Shapely algorithm to show that there is a stable matching for each possible set of preferences. They proceed to prove things things about the algorithm–for instance that women, once proposed to, always remain engaged; that women only move down their preference list as the algorithm progresses; and so on and so forth. It all builds up to the proof that the matching returned by the algorithm is stable.

Then, for cases where more than one stable matching is possible, they explore a way to characterize the different stable matchings. On the way, they prove that every execution of the Gale-Shapely algorithm yields the same stable matching. Specifically, it always gives the men their “best valid partners” and the women their “worst valid partners.” Darn patriachy.

Then, they briefly introduce the concept of graphs, and proceed to introduce five “representative problems” in terms of graphs, in ascending difficulty, explaining the basic concepts and special difficulties underlying each.