1
$\begingroup$

We have a club with $\frac{s(s+1)}{2}$ people, and we know that no matter how we choose $3$ of them, there are at least $2$ of them, who know each other.

Prove, that if this is true, then we can always choose $s$ people, where all of them know each other. In graph language, we have a graph with $\frac{s(s+1)}{2}$ vertices, and we draw edges if $2$ people know each other. No matter how we choose $3$ vertices, we always find at least $1$ edge. Prove, that this graph has $K_s$ in it($s$ vertices with all possible edges drawn).

I tried to prove this in different ways, but just can't conclude why is it true, maybe it can be solved with Ramsey's theoerem?

Any ideas? Thanks!

$\endgroup$
2
$\begingroup$

Indeed, you want to colour edges in your given graph by blue, and all non-edges by red. This gives a red-blue colouring of the edges of $K_{{s+1\choose 2}}.$

Really, the main point is to show that that $R(3,s)\leq {s+1\choose 2}$, where $R(3,s)$ is the smallest $n$ so that any red-blue colouring of the edges of $K_n$ has either a red $K_3$ or a blue $K_s$. Since you are given that your graph has no red $K_3$, you can conclude that it has a blue $K_s$.

To show that upper bound, use induction and the inequality $$R(r, s) \leq R(r − 1, s) + R(r, s − 1)$$ for all $r,s$. Also, notice that $R(2,s)=s$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.