6 People, 3 Mutual Friends / Strangers

Problem: Assume every two people are either friends or strangers. Prove that if six people get in a room, there's always either three mutual friends or three mutual strangers.

Consider some arbitrary person (P_1), who is friends with k people and strangers with 5-k people, for k∈{0,1,2,3,4,5}.

Case I: k=0

(P_1) is mutual strangers with everyone else: (P_2),(P_3),(P_4),(P_5),(P_6).

• If some pair in {(P_2),(P_3),(P_4),(P_5),(P_6)} are mutual strangers, then there is a set of three mutual strangers: (P_1), and that pair.

• If no pair in {(P_2),(P_3),(P_4),(P_5),(P_6)} are mutual strangers, then they must be all mutual friends. Thus there is a set of three mutual friends among these five people.

Case II: k=1

(P_1) is mutual friends with (P_2), and strangers with (P_3),(P_4),(P_5),(P_6).

• If some pair in {(P_3),(P_4),(P_5),(P_6)} are mutual strangers, then there is a set of three mutual strangers: (P_1), and that pair.

• If no pair in {(P_3),(P_4),(P_5),(P_6)} are mutual strangers, then they must all be mutual friends. Thus there is a set of three mutual friends among these four people.

Case III: k=2

(P_1) is mutual friends with (P_2),(P_3), and strangers with (P_4),(P_5),(P_6).

• If some pair in {(P_4),(P_5),(P_6)} are mutual strangers, then there is a set of three mutual strangers: (P_1), and that pair.

• If no pair in {(P_4),(P_5),(P_6)} are mutual strangers, then they must all be mutual friends. This is the set of three mutual friends.

Case IV: all other cases

• k=3: We can make the same argument as k=2 if we relabel "friends" and "strangers", and obtain the same conclusions as above (with the labels swapped).

• k=4: We can make the same argument as k=1, same relabeling as above.

• k=5: We can make the same argument as k=0, same relabeling as above.