I'm trying to prove that it is impossible for every man to be paired with their last choice in the stable marriage algorithm. I have a general idea of how to approach it, which is:
Suppose there exists a stable pairing T in which every man is paired with his least favorite woman, also suppose it took K days for the algorithm to halt. This means that on every day before the Kth day every man had been rejected by every woman. However, it is impossible for every woman to reject every n-1 men. If the algorithm halts on the Kth day then there has to be at least one woman who has not yet received a proposal on the K-1th day. Therefore, on the last day there is a woman who receives only one proposal and cannot reject it. Consequently, such stable pairing T does not exist.
Is this logically correct? I know I probably need to refine it a bit.
Suppose there is such a pairing for $n$ pairs of men and women. Let $d$ be the earliest round when there is a man to pair with his woman of his last choice. One of such men is thus rejected by his more favored $n-1$ women who having ever been proposed to are all engaged by the $d-1$'th round. All the other men are by this reason engaged. The woman of his last choice has not ever been proposed to by any man by the $d-1$'th round. Otherwise she would have been engaged by then and all women would have been engaged and the algorithm ends on round $d-1$ which is impossible. On round $d$ only that man is left to propose. He proposes to that woman. Since that woman is not engaged, it does not affect all the pairings having already formed by round $d-1$. Round $d$ is thus the ultimate round. All the other $n-1$ men favor the women they are paired to more than this woman last proposed to. We have a contradiction.