A school class has 90 students, each of whom has ten friends among(adsbygoogle = window.adsbygoogle || []).push({});

the other students. Prove that each student can invite three people at a

restaurant so that each of the four people at the table will know at

least two of the other three.

If this had to be translated to a graph it would have 90 vertices and each vertex would have 10 edges to represent friendships. I assume that when a person invites 3 other people he has an edge connecting him to the other three, so this means within such a group of 4 everybody knows at least 1. I guess the solution will have to involve the Pigeonhole principle in some form.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Graph Theory and Pigeonhole Principle

**Physics Forums | Science Articles, Homework Help, Discussion**