In Words

The boys propose (to their top-ranked girl that hasn't yet rejected them) and the girls tentatively accept. This is an engagement.

If a girl ever gets an offer from a boy that she likes better than her current fiance, she breaks her old engagement for him.

Stop when all boys are engaged.

M holds the tentative matching. $\mbox{rejected}[b]$ records the rank position of b's most recent rejection (ouch).

Once b is rejected by g, b never needs to propose to g again. Why?

(It is possible to also have the girls do the proposing... we will return to this later.)

Example!