Prove that if man x is paired with woman a in some stable matching, then a

does not reject x in the proposal algorithm with men proposing. (Hint: Consider the first

occurrence of such a rejection.)

Conclude that among all stable matchings, every man is happiest in the matching

produced by this algorithm.

Thanks for any advice!