IMO ShortList 2001, combinatorics problem 3
Source: IMO ShortList 2001, combinatorics problem 3, HK 2009 TST 2 Q.2
September 30, 2004
combinatoricsgraph theoryClique numberIMO Shortlist
Problem Statement
Define a -clique to be a set of people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.