More Theorems

We will soon prove a number of important facts about this algorithm.

• Theorem 3: For every girl g, $\mbox{\sc Rank}(R_G[g], M_G[g])$improves (decreases) throughout the execution of $\mbox{\sc Match}$.
• Theorem 4: The order in which the boys are chosen to propose doesn't matter (you get the same marriage no matter what).
• Theorem 5: The algorithm will terminate before the ROL of any boy is exhausted.
• Theorem 6: The returned matching is stable.
• Theorem 7: The boys get to marry the best girl that they could possibly get in any stable marriage. The matching is simultaneously optimal for all of them!