# Need help understanding stable matching proof

In the above proof, I couldn't understand the reason given for why every boy can't rate some girl $A$ worst. First they are talking about some girl $A$ and later in the reason they are talking about each of the $n$ girls being rated worst by at least $n-1$ boys.

Can someone explain me this proof.

• It seems this implicitly assumes there are no "ties": otherwise, if every boy prefers every girl equally, and vice versa, then any pairing would be stable. – Daniel Schepler Feb 13 '18 at 20:31

## 1 Answer

There are only $n$ boys, so there are $n$ total "worst" labels to distribute among the $n$ girls. That's simply not enough to give each of the $n$ girls $n-1$ or more "worst" labels. Therefore there must be at least one girl who gets fewer than $n-1$ "worst" labels.

They're not saying that it's impossible that every boy dislikes the same girl. They're saying that there must be at least one girl who doesn't get too many dislikes.

• This answer is correct, but to address your specific question: The proof does not say “every boy can't rate some girl $A$ worst.” In fact, there can be a girl whom every boy rates worst. That girl will have $n$ “worst” labels. But then every other girl will have zero “worst” labels, and one of those other girls can be the one we’ll call $A$. – Steve Kass Feb 13 '18 at 20:18