Lower bound for the Ramsey number $r(k,k)$

Question

I'm trying to prove the following inequality for every natural $k$:

$$r(k,k)>(k-1)^2$$

I was trying to find a blue-red edge coloring of $K_{(k-1)^2}$ without either red or blue $K_k$.

Any ideas?

Answer 1

HINT: Label the vertices of $K_{(k-1)^2}$ with the ordered pairs from $[k-1]\times[k-1]$. The edge between $\langle i,j\rangle$ and $\langle m,n\rangle$ is red if $i=m$ and blue otherwise.

Answer 2

First make sets of k-1 vertices such that no vertex joins more than one set. Now make all sets monochromatic, let's say red. Now we can't have a blue set greater than the amount of red sets, because we can't use more than one vertex of a red set to make a blue set, since the two vertices of the red set are connected by a red edge.