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

  • $\begingroup$ 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. $\endgroup$ – Marc Dec 1 '14 at 18:54
  • $\begingroup$ Out of curiosity, how's the proof end? $\endgroup$ – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.