acquaintances
Source: Ireland 2002
July 5, 2009
combinatorics proposedcombinatorics
Problem Statement
A group of people attends a party. Each person has at most three acquaintances in the group, and if two people do not know each other, then they have a common acquaintance in the group. What is the maximum possible number of people present?
If, in addition, the group contains three mutual acquaintances, what is the maximum possible number of people?