# Coloring of complete graph $K_n$ that has no monochromatic $K_k$?

Let $$k \geq 3$$ and $$n = (k−1)^2$$. Give an explicit 2-coloring of the edges of $$K_n$$ that does not have a monochromatic $$K_k$$.

My thoughts were to partition the graph into k-1 subgraphs each with k-1 many vertices and color all edges connecting vertices of the same subgraph as red, and all edges connecting vertices of different subgraphs blue.

Does this work?

• It does work. It's clear from construction that there is no red $K_{k}$ but I would explain more carefully why there is no blue $K_{k}$. Specifically, pick (any) $k$ vertices and use the pigeonhole principle to prove that two of them must lie in the same subgraph, ie their are connected by a red edge; hence the $k$ vertices do not form a blue $K_{k}$. (Note that in order to take $k$ vertices, you need $k\leq(k-1)^2$; that's why we need $k\geq 3$) Feb 28, 2020 at 16:17

Index the $$n=(k-1)^2$$ by the ordered pairs $$(i,j)$$ where $$i,j=1,2,\cdots,k-1$$. Now join the pairs $$(i,j)$$ to $$(i,j')$$ with red edges and also join the pairs $$(i,j)$$ to $$(i',j)$$ with red edges. join all other edges with blue edges.
Claim there will not be any monochromatic $$K_k$$. It is reasonably easy to see that there will be lots of red $$K_{k-1}$$'s but any further element will cause a blue edge to be included, so there are no red $$K_k$$'s.
Now a blue $$K_k$$ will need to be $$k$$ vertices $$(i_1,j_1),\cdots,(i_k,j_k)$$ where all the $$i$$'s are distinct which is impossible (by the pigeon hole principle), so there are no blue $$K_k$$'s.