Problem
COM-B1-M11-P021 Three Acquaintances
#21
★★★★☆ Level 4 of 5
In a group of \(10\) people, each person knows at least \(6\) others. Prove that there are three mutual acquaintances.
Choose one person and look at their acquaintances.
Let \(A\) be any person. This person has at least \(6\) acquaintances. If among these acquaintances there is an acquaintance pair, then together with \(A\) we get a triple. If there are no acquaintance pairs among them, then each of these \(6\) people knows \(A\) and can know only the three people outside this set and outside \(A\), so their degree is at most \(4\). This contradicts the condition that every degree is at least \(6\).
Extremal graph argument.