Every $14$-vertex clique has $3$ people who know each other or $5$ who don't know one another.

Question

Ramsey theorem says that the smallest number $n$ such that in $n$-vertex clique there are always 3 people who know each other or 5 people who doesn't know each other is equal to $14$. I've seen proofs of $R(3, 5) = 14$, but they were giving some upper/lower bounds on $R(3, 5)$ based on values of some other $R(a, b)$. I'm interested how to prove that $14$-vertex clique is indeed a graph where 3 people know each other or 5 people who don't know one another.

Answer 1

I think you have to build it up a bit, because otherwise you lose track of what is going on.

Amongst any six people there are three who know each other or three who are mutual strangers. We can see this by taking an individual and examining who he (or she) knows - there are five other people, and if he knows more than half, he knows at least three. If any pair of these know each other we have three mutual acquaintances (the original person plus the two who know each other). If none of the three know each other they are three mutual strangers. The argument in reverse operates if the first person knows fewer than half of the others.

Now we show that amongst any nine people there are either three mutual acquaintances or four mutual strangers. Take one of the people. If he doesn't know as many as six of the others, then amongst those six there are either three mutual acquaintances (we are done) or three mutual strangers, who we can add to the first person to make four. If a person knows as many as four others, then either a pair of these know each other and we have three acquaintances with the first person, or no pair does, and the four are mutual strangers.

So the only case we have not covered is if none of the nine know more than three people and none is a stranger to more than five - so each must know exactly three. However, these relationships are mutual, and come in pairs, while $9\times 3$ is odd. So there must be at least one person who knows more than three or is a stranger to more than five, and the case cannot arise.

Next, we consider $14$ people. Suppose person $1$ knows as many as five others. Then if any pair of these know each other, there are three mutual acquaintances, and if none do there are five mutual strangers. So this person must know at most four people and be a stranger to at least nine. Amongst nine there will either be three mutual acquaintances (and we are done) or four mutual strangers, who make a group of five when we include the original person we chose.

This does not prove fourteen is the minimum, (nor six nor nine) - and therefore does not fix the Ramsey numbers, but it does do what you want.