For some n ≥ 3 there exists a set of n boys, n girls, and preference lists for every boy and girl such that every possible boy-girl matching is stable. If true, give a proof. If false, give a refutation.
This is obviously false as at n=3 I can find a unstable matching. But then I need to prove it for n≥3, no stable matching will appear.
I tried doing it like this: Assume I keep adding a stable pair of couples starting at 3 pairs, no matter how many pairs I add the matching remains unstable as an unstable pair already exist in the group. But what if I added unstable couples, then I cannot promise at some n the matching might suddenly become stable.
So is there a way to prove it?
You're asking about the Stable Marriage Problem.
Not only does there exist a stable setting, but you can also find it in ($n^2$) time! First you fix a sex that "proposes", say men. Then every man, one after another, proposes to his first-choice woman. They accept provisionally. If, at a later point a woman, who has already accepted a proposal, gets an offer from a higher-preferred man, then she boots her first choice out. The rejected enters the loop again, then asking for his next-highest choice.
Now you only need to prove that the algorithm terminates, that everyone's married then and that the constellation is stable.