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