Lesson 12

Let's give an example.

The man \(A\) proposes to the woman \(H\). She is free, so she agrees. The tail of her preference list will be erased because she will never need it again.

The man \(B\) proposes to a woman \(F\), she agrees.

After that, the man \(C\) proposes to \(I\), she agrees.

The man \(D\) proposes to the woman \(F\). She refuses, since she is paired with \(B\), whom she likes more.

The man \(D\) proposes to the woman \(H\). She is paired with \(A\), but she likes \(D\) more, so she accepts \(D\)'s proposal, and \(A\) becomes free.

And so on. After several steps, the following perfect matching is produced. Below we will prove that it is stable.