[Math] Prove that at most one man obtains his worst choice in stable matching algorithm

Question

For the Stable Matching algorithm by Gale-Shapley, how do I prove that at most one man will get his worst choice?

My intuition is that I have to use contradiction. Assume that there are two men who will get their worst preferences: $M_1$ with $W_1$ and $M_2$ with $W_2$. I have to prove $M_2$ and $W_2$ are unstable. However, I can't think of anything. Can anyone help me with the proof?

Thanks!

Answer 1

Suppose $M_1$'s last choice is $W_1$ and $M_2$'s last choice is $W_2$. Before they are forced to select $W_1$/$W_2$ respectively, the Gale–Shapley algorithm has already directed $M_1$/$M_2$ to propose to all women other than $W_1$/$W_2$. Thus all women have been proposed to, so are now engaged, so the algorithm stops. But we assumed that the algorithm does not stop here, so we have a contradiction and at most one man can have his worst choice.