A high school has 90 alumni, each of whom has ten friends among the other alumni. Prove that each alumni can invite three people for lunch so that each of the four people at the lunch table will know at least two of the others.
I know each vertex has degree 10 and its a simple graph with the pigeonhole principle working its way in there somehow. Any help would be appreciated.
On
Pick any vertex v. It is connected to 10 vertices. Keep these 11 vertices aside. We are left with 79 vertices on the other side.
Realize that the central case is when we have five disjoint pairs(that is, each pair consists of distinct vertices) of edge connected vertices among the 10 vertices v is connected to. Thus we have 5 triangles with v being the only common vertex in each of them.
Case 1: if we have an extra edge between any two of the ten vertices, we can obtain a square or a figure similar to having two triangles with a common base, either of which gives us the set of four required vertices.
Case 2: if not we have at least 80 edges(this' the reason I called it the central config. At present there's 8 edges for each of the ten vertices v's connected to. If I subtract an edge from here the no. 80 will increase. If I move away from the idea of 5 distinct pairs using 5 or more edges within the 10 vertices v is connected to, I will land in case 1.) emanating out of our set of 11 vertices towards the set of 79 vertices. By PHP, at least 1 of the 79 vertices is connected to two of the ten vertices leading to a square.
Pick a vertex $v$. This vertex is connected to $10$ other vertices $v_1,..,v_{10}$.
There are 89 vertices different of $v$. Each of the vertex $v_1,..,v_{10}$ is connected to $9$ of the other $89$ vertices. Thus there are 90 edges leaving towards the $V \setminus \{v\}$.
Thus two of edges leaving $v_1,..,v_{10}$ have a common end vertex $w$. Let $v_iw$ and $v_jw$ be these two edges.
Now show that if $v$ invites $v_i, v_j, w$ it solves the problem.