# Graph Theory Question about People at a Party

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.) :

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

• Because, by assumption, there are at most $m-1$ people who mutually cannot know each other. Thus for every $m$ people at least one guy knows one of the others, which is represented by the edge. – Marc Dec 1 '14 at 18:54
• Out of curiosity, how's the proof end? – Simon S Dec 1 '14 at 18:59

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).