As simple as the algorithm is, its behavior is not immediately
obvious.
Let's show that no boy can be rejected by all girls.
- A boy b is only rejected by a girl who is already engaged (not
to him).
- So, the last rejection for b can only come if all n girls are
already engaged to someone better.
- But there can only be n-1 boys better than b, so this can't
happen.
This proves Theorem 5: the algorithm terminates before the ROL of
any boy is exhausted. We get a marriage!
Next: Correctness
Up: UNDERSTANDING THE ALGORITHM
Previous: UNDERSTANDING THE ALGORITHM