Page "Stable marriage problem" Paragraph 14

; The marriages are stable: Let Alice be a woman and Bob be a man who are both engaged, but not to each other.

Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners.

If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner.

If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner.

If Alice rejected his proposal, she was already with someone she liked more than Bob.