Discussion 1 Solved

    1. Prove that every execution of the G-S algorithm (when men are proposing) results in the same stable matching regardless of the order in which men propose.


    2. Prove that when we run the G-S algorithm with men proposing, women end up with their worst valid partners.

    3. True or False:

In every stable matching that Gale–Shapley algorithm may end up with when men propose, there is a man who is matched to his highest-ranked woman.


    4. In a connected bipartite graph, is the bipartition unique? Justify your answer.