Correctness

Furthermore, the final marriage is stable (Theorem 6). Proof by contradiction.

• Assume that there is some pair (b,g) that prefer each other to whomever they are matched to.
• Since b proposes strictly in order of his ROL, this means that he must have proposed to g at some point.
• Since b isn't engaged to g, that means g must have rejected b.
• But, g would only reject b for someone she ranks more highly.
• Therefore, by Theorem 3, g's final fiance is ranked more highly than b.
• Therefore g doesn't prefer b to her mate. Contradiction!

Since the algorithm always terminates (Theorem 5), and the returned matching is stable (Theorem 6), then there is always a stable marriage, for any well-formed set of ROLs (Theorem 2). Note that this is a proof by algorithmic correctness!