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 womens 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 arent 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.