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**

Join Physics Forums Today!

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

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**