Could one be a friend of all?

Question

The social network "ILM" has a lot of members. It is well known: If you choose any 4 members of the network, then one of these 4 members is a friend of the other 3.

Proof: Is then among any 4 members always one who is a friend of all members of the social network "ILM"?

Note: If member A is a friend of member B then member B is also a friend of member A.

I don't find an approach right now. Any kind of help or advice will be really appreciated.

Answer 1

HINT: Let $P$ be the set of members. For $p,q\in P$ I’ll write $p\sim q$ to indicate that $p$ and $q$ are friends, and $p\not\sim q$ to indicate that they are not.

Suppose first that there are three people, $p,q$, and $r$, such that $p\not\sim q$ and $p\not\sim r$.

• Show that if $s\in P\setminus\{p,q,r\}$, then $s\sim p$, $s\sim q$, and $s\sim r$.
• Then show that if $s,t\in P\setminus\{p,q,r\}$, and $s\ne t$, then $s\sim t$.
• Conclude that among any four members of $P$ there is always at least one who is friends with every other member of $P$.

Now suppose that if $S$ is any $3$-member subset of $P$, then there is at least one $p\in S$ who is friends with both other members of $S$. Suppose further that $p$ and $q$ are two members of $P$ who are not friends.

• Argue very much as in the first case to show that every member of $P\setminus\{p,q\}$ is friends with every other member of $P$.

Answer 2

Suppose there isn't a person who knows everyone.

Then take vertex $v$, he doesn't know everyone, in particular there is a $w$ he does not know.

If $w$ doesn't know anybody we are done, if he does select a friend of $w$, Preferably somebody who does not know somebody besides $v$ (if everybody that knows $w$ knows everybody except possibly $v$ you can argue that everybody who knows $w$ does not know $v$, hence you can pick any other two vertices and there will be no one knowing all three). So suppose there is a friend of $w$ called $u$ that does not know someone else called $t$. In the group $v,w,u,t$ there is no one who knows the rest.