4. For each of the following claims, state whether the claim is true or false, and give a short proof to justify your answer (i.e., either a brief argument why it is true or a counter-example showing that it is false). Note: By a stable marriage instance, we mean an input for stable marriage, i.e., the sets of men and women and their preference lists.

(a) In a stable marriage instance, if man M and woman W each put each other at the top of their respective preference lists, then the Gale-Shapely algorithm is guaranteed to match M with W.

(b) In a stable marriage instance with at least two men and two women, if man M and woman W each put each other at the bottom of their respective preference lists, then the Gale-Shapely algorithm will never match M with W.