Define a -clique to be a set of people such that every pair of them know each other (knowing is mutual). At a certain party, there are two or more -cliques, but no -clique. Every pair of -cliques has at least one person in common. Prove that there exists at least one, and not more than two persons at the party, whose departure (or simultaneous departure) leaves no -clique remaining.
, 1997
Solution
We consider two cases.
Case 1. There exist two -cliques sharing two common people.
Suppose the two -cliques are and . If all -cliques contain or , we are done as we can remove and . If there exists a -clique without and , it must be since every pair of -cliques has a common person. We claim that there is no -clique if and are removed.
Indeed, note that , and are existing -cliques since all pairs of people in these -cliques know each other from above. Therefore, the only possible -clique without and is . Then forms a -clique, which is a contradiction.
Case 2. Any pair of -cliques shares exactly one common person.
Suppose two -cliques are and . If all -cliques contain , we are done as we can remove . If there exists a -clique without , it must be up to renaming of the people. Then we have a -clique sharing two common people with . This is a contradiction.
The proof is complete since all cases are covered.