Prove that in any group of 6 people, some 3 are mutual acquaintances or some 3 are mutual strangers, exhibit a group of 5 where neither happens, and state the exact threshold.

Prove that in any group of 6 people, some 3 are mutual acquaintances or some 3 are mutual strangers, exhibit a group of 5 where neither happens, and state the exact threshold.

Approach: Fix one person and split his five relationships into two classes, then apply the pigeonhole principle to the larger class and check the relationships inside it.

6. Fix one of the 6 people. He has 5 relationships, each an acquaintance or a stranger, so by pigeonhole at least 3 lie in one class, say he knows A, B and C. If any two of A, B, C know each other, that pair with him is a mutual acquaintance triple. If no two of them know each other, A, B and C are mutual strangers. Swapping the two classes runs the same argument, so 6 always forces one or the other. Five people can avoid it: seat them in a circle, let each know his two neighbours and be a stranger to the other two. That two colouring makes both the acquaintance graph and its complement a 5 cycle, and a 5 cycle is triangle free. So the threshold is exactly 6.

Follow-up: What is the smallest group that forces either 4 mutual acquaintances or 3 mutual strangers?

Key concepts: pigeonhole, triangle free graph, two colouring.