Graph Theory and Pigeonhole Principle

A school class has 90 students, each of whom has ten friends among
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.

akit

Here's my solution:

Take any guy call him x. Say he has 10 friends y1,y2,....y9,y10.

Now, there are 89 people in total not including x. Each y_i for i = 1,2,...10 has 9 other friends not including x. Since there are 10 y_i guys and they each have 9 friends other than x there are 90 non-x "friends of friends of x" let's say (possibly including duplicates)and only 89 unique non-x people. Hence by the pigeonhole principle, the 90 "friends of friends of x" can't be all unique.

Hence there exists some a,b in {1,...,10 } such that both y_a and y_b have some same friend, say z. z is not x. z is neither y_a or y_b since y_a and y_b can't be friends with themselves.

So you have four unique people:

x, y_a, y_b, z

x is friends with y_a and y_b
y_a is friends with y_b and z
y_b is friends with y_a and z
z is friends with y_a and y_b

and we are done.