In 1990 people, each one is connected to at least 1327 others, then there is a fully-connected 4-group of people

Question

We have 1990 people and each one is "connected" to at least 1327 others. Show that there is a group of 4 people where each one is "connected" to every other person of that group.

We could model the relation "connected to" as a graph, where each node is a person (so $n=1990$ in $G(V,E)$) and two people $u,v$ are connected iff $u,v\in E$. Then from the problem statement, $δ(G)\geq 1327$ and thus $m\geq 1327$. We need to show that $G(V,E)$ has the complete graph $K_4$ as a subgraph, i.e. $K_4\subset G$. But I am stuck here. Any help to advance my solution?

Answer 1

First you can show that there is a clique of size 3 - a set of 3 people, each of whom is connected to the other two. Take a pair of people who are connected. Each one is connected to at least 1326 others. $1326 + 1326 = 2652 > 1988$ so these two people must have at least one connection in common.

Once you know there is a clique of size 3 you can extend the same argument to show there is a clique of size 4 as follows:

(1) Consider any pair within the size 3 clique. Work out how many connections that pair must share outside of the clique.

(2) Consider all 3 pairs within the size 3 clique. Show that the 3 pairs must have at least one shared connection in common. Add this connection to the size 3 clique and you have a size 4 clique.

Answer 2

I just assumed that as each pair of the size 3 clique connects with 664 other vertices, and if we except v1,v2,v3 there are 663 other vertices we can conclude in a size 4 clique. (There are 1990 nodes, 1987 if we put out v1,v2,v3, and 3*663=1989. Therefore at least two pairs of the size 3 clique have a common node)

Answer 3

Each person is connected to at least 1327 of the other 1989 people. So each person is disconnected from at most $1989-1327=662$ of the others. Pick one person arbitrarily, and call him person A; he'll be the first of the four mutually connected people that I'll find. All the people he's disconnected from can be sent away, since they can't be among the desired four. The people that remain are A and the 1327 or more people he's connected to.

Pick arbitrarily one of those 1327 people, and call her person B; she'll be the second of the four mutually connected people that I'll find. All the people she's disconnected from can be sent away, since they can't be among the desired four. We've just sent away at most 662 people. The people that remain are A, B, and at least $1327-1-662=664$ others. (The subtracted $1$ is B; the subtracted 662 are the ones we just sent away.)

Pick arbitrarily one of those 664 or more others, and call him person C; he'll be the third of the four mutually connected people that I'll find. All the people he's disconnected from can be sent away, since they can't be among the desired four. Of the 664 people (other than A and B) that remained at the end of the previous step, one has been renamed C, and at most 662 others have just been sent away. So at least one remains. Call her D.

Then A, B, C, and D are all connected. Proof: If any two of them were disconnected, the later of the two (in alphabetical order) would have been sent away right after the earlier of the two was chosen.

Answer 4

Let $A$ be a set of all neighbors of vertex $a$.

By PIE we have for any two vertices $a$ and $b$:

\begin{align}1990& \geq |A\cup B| \\&= |A|+|B|-|A\cap B|\\ &\geq 2\cdot 1327-|A\cap B|\end{align}

So, for any pair of vertices we have: $$|A\cap B|\geq 664$$

Now take any three vertices $a,b,c$ and let $X=A\cap B$, then \begin{align}1990& \geq |X\cup C| \\&= |X|+|C|-|X\cap C| \\& \geq 664 +1327-|X\cap C|\end{align}

so $$|A\cap B\cap C|= |X\cap C|\geq 1$$

which means that any thre $a,b,c,$ have common neighbour and we are done.