Stable matching with constraints I'm reading through Algorithm Design by Kleinberg and Tardos and was working on Ch1 Q1. The question is about stable matching and their 'proof' is presented by contradiction. I have an alternative argument and want to know if its right. The question paraphrased is:


  Consider a town with n men and n women. Each man as a preference list
  that ranks the women and each women has a similar preference list. Of
  these men and women, k men are bad and k women are bad. So there are
  n-k good women and n-k good men. Each man prefers to match with a good
  women and vice versa. Therefore all preference lists rank the good
  people higher than bad people. Show that in every stable matching
  every good man is married to a good women.


My 'proof':

Assume that there is a pairing where a good man is matched with a bad women. Because there are the same number of good men and women, it means that there is one good woman, currently paired with a bad man, who rejected this good man. If she rejected this good man it means that he must be of lower preference than the bad man she is paired with. But this is a contradiction because a good man cannot be ranked lower than a bad man. It means that the good man is actually bad and there are more bad men than good women and the initial problem statement is false.
I assume you want to start your proof with "suppose there is a pairing where a good man $m_1$ is matched with a bad woman $w_1$".

This indeed means that there exists a good woman $w_2$ matched with a bad man $m_2$ (by the pigeonhole principle). However, the contradiction here does not follow from the fact that $w_2$ prefers $m_1$ but is actually matched to $m_2$ (it is possible for a woman to not be matched with her top ranked man).

The contradiction follows from the fact that a matching which contains $(m_1,w_1),(m_2,w_2)$ is not stable, since $m_1$ prefers $w_2$ and $w_2$ prefers $m_1$.