Stable Marriage problems

Problem 4. (10 points) Let I be an instance of STABLEMARRIAGE with all men having identical preference lists. Show that I has exactly one stable matching Problem 5. (10 points) For STABLEMARRIAGE what is the minimum and maximum number of proposals Propose-Dispose will perform for N 2, N = 3, N = 4, and for an arbitary value of N? Find an instance that achieves the minimum. Show that no other instance can be less. Find an instance that achieves the maximum. Show that no other instance can be greater Problem 6. (10 points) For the STA BLEMARRIAGE problern with n = 2 (two men and two women) is it possible for all matchings to be stable? What if n 3? For each question either state yes and give an instance with al matches stable or state no and prove it cannot occur