Consider the stable matching problem discussed in class. Here is a simple and natural

idea to find a stable matching. Start with an arbitrary perfect matching, which is of

course easy to construct. Test whether it is indeed a stable matching. If so$,$ print it and

you are done. If not, there is an unstable pair with respect to it$.$ In order

to promote stability, allow this unstable pair to marry each other after divorcing their

current partners. Also, conduct a marriage between the two divorced folks so that no

one is left alone. Obviously, we now have a new perfect matching. Check whether this

perfect matching is stable. If so$,$ you are done. If not, there is an unstable pair with

respect to it and so$,$ we can repeat the process. A sample pseudocode to implement

the above idea is shown below.

image.png

Needless to say that the above pseudocode indeed produces a stable matching, if it

terminates. However, there is no guarantee that it will terminate $($and so$,$ it is not

really an algorithm$).$ Construct a counterexample, to demonstrate that the above

pseudocode will not necessarily terminate. Clearly show the preference list of men and

women and an initial perfect matching for your counterexample. Then demonstrate

that the pseudocode does not terminate by tracing the execution. Also, specify an

actual stable matching for your counterexample, even though the above pseudocode

cannot find it$.[$Hint: Can construct a counterexample with just three men and three

women $($even though there is no restriction on the number of men and women in the

counterexample that you are submitting$).]$