2-coloring of R(m,m) with no monochromatic $K_m$

Question

I am working on a pset question on Ramsey numbers and trying to prove the following question:

Let $m \ge 3$ be a positive integer. Construct a red/blue coloring of $K_{(m-1)^2}$ which has no monochromatic $K_m$ (i.e. show that $R_{m,m} \ge (m-1)^{2} + 1$.

Here is my rough draft where I am trying to conceptualize the answer. However, I am new to the subject of graph theory and would appreciate any feedback on how to proceed.

=========================

To construct a $K_{(m - 1)^2}$ that does not have a monochromatic $K_m$, we need to show that there is a 2-coloring of $K_m$ that contains neither a red monochromatic $K_m$, nor a blue monochromatic $K_m$. We will count the colorings of $K_m$ that contain either a red or a blue monochromatic $K_m$. \

Let $S$ be a subset that has $\textit{m}$ vertices and Let $S_2$ be the set of 2-colorings of $K_m$ where the subgraph induced by \textit{S} is either all blue or all red. We can count the number of colorings in $S_2$ as we know that there are two ways to color the edges in the subgraph induced by $\textit{S}$ so that it is monochromatic. Then, we see that the number of 2-colorings containing either a red $K_m$ or a blue $K_m$ corresponds to the cardinality of the union of all the $S_2$'s for all possible subsets $textit{S}$ containing $\textit{m}$ vertices. We know that the union cannot be larger than the sum of the sizes of the sets. Then, the number of 2-colorings containing a monochromatic red or blue $K_m$.... (incomplete)

Then, there must be a 2-coloring of $K_m$ such that it contains no monochromatic coloring of $K_m$ and we can conclude that $R(m,m) \ge (m - 1)^2 + 1$.

Answer 1

You are trying to give a non-constructive proof that a legal coloring exists. Sometimes this is a useful method, but I do not see it working out here. You will probably be better off trying to find an explicit coloring.

Here is a (big) hint for finding a coloring. Arrange the vertices in a $(m-1)\times (m-1)$ grid, and color the edges so that every row is a red $K_{m-1}$.

Answer 2

Split the vertices into blocks of size $m-1$, color edges between vertices of the same block red and between vertices of different blocks blue.

If we select $m$ vertices there must be two of different blocks and thus a blue edge, there must also be a block with two or more vertices and thus a red edge.