The previous argument exemplifies a proof technique typical of this subject. Then by reasoning about particular individuals we deduce a contradiction which then forces a conclusion that applied equally to everyone. We've seen that the algorithm always produces a matching. In keeping with the comment just above, we shall assume the contrary and work for a contradiction. Now consider the run of the algorithm.
Men propose to women one by one, working down their preference lists.
Many students at first find proof by contradiction difficult to swallow. On the other hand, if you can do without contradiction, often that clarifies your argument. To illustrate, let's redo the previous proof in strictly positive terms. So either way, we don't have an adulterous pair. In other words, no single man can do better in any other stable matching.