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!