Studying for final exams, I was given a practice question which goes as follows:
There are (m − 1)n + 1 people at a party. Show that either there are m people,
no two of whom know each other, or there is a person who knows at least n others.
Later, the professor gave us the answer to the question as follows (I am only posting the beginning of the answer.) :
Prove it by contradiction.
Use (m − 1)n + 1 nodes to represent the people, and if two people know each other, there is a edge between the two nodes. Assume that there are at most m − 1 people who mutually do not know each other, and each person knows at most n-1 others.
Then every m nodes must have at least 1 edge.
Why is the final statement true? Why must every m nodes have at least one edge?
EDIT: https://www.math.ucdavis.edu/~thompson/soln6.pdf <– Link to rest of proof, it is number 7.3.13
Best Answer
This follows from the assumption that $m-1$ is the maximum size of an independent set (maximum number of people no two of whom know each other). If we consider more than $m-1$ people, at least two know each other (there is at least one edge).