Discussion 1
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.