In Solved Exercise 2 (p. 19 of Kleinberg), our book modifies the code for Gale- Shapley. Let us instead solve the problem using the following reduction to the standard stable matching problem. - Given an instance where some pairs are forbidden, move the forbidden part- ners of each man to the bottom of his list without disturbing the relative order of the other women in his list. Perform the analogous operation the women's lists. - Find a standard stable matching S for these lists. - Remove all forbidden marriages in S, and return the set S' of matchings that are left. The people that aren't in a marriage in S' are single. Prove by contradiction that S' is stable under the new definition of stability that is given on page 20 of the Kleinberg text. To do this, assume S' violates one of the stability conditions of the new problem. In each case, show that S is also unstable, contradicting how S was chosen. In Solved Exercise 2 (p. 19 of Kleinberg), our book modifies the code for Gale- Shapley. Let us instead solve the problem using the following reduction to the standard stable matching problem. - Given an instance where some pairs are forbidden, move the forbidden part- ners of each man to the bottom of his list without disturbing the relative order of the other women in his list. Perform the analogous operation the women's lists. - Find a standard stable matching S for these lists. - Remove all forbidden marriages in S, and return the set S' of matchings that are left. The people that aren't in a marriage in S' are single. Prove by contradiction that S' is stable under the new definition of stability that is given on page 20 of the Kleinberg text. To do this, assume S' violates one of the stability conditions of the new problem. In each case, show that S is also unstable, contradicting how S was chosen