Prove that a one-color $K_4$ exists in a two-color $K_{18}$

An edge coloring of a graph is an assignment of colors to the edges of the graph. I have $K_{18}$ colored with blue and red and I want to show that it contains a $K_4$ colored with just one color. Also I want to prove that it is the best possible.

I know this question is related to Ramsey-theory, but I don't want to use it.

• You can have multicharacter subscripts by using curly braces. k_{18} would work if that is what you intended. – Matt Samuel Feb 5 '16 at 0:43
• @MattSamuel thanks dude :) – Arman Malekzadeh Feb 5 '16 at 0:44
• You're welcome. – Matt Samuel Feb 5 '16 at 0:45
• I think we need computers for this. – Yorch Feb 5 '16 at 1:30
• @dREaM no i'm sure we don't because our teacher told us to prove it :) – Arman Malekzadeh Feb 5 '16 at 1:40

We first prove $R(4,3)\leq 9$. In other words, if $K_9$ is colored red and blue there is a red $K_4$ or a blue $K_3$.

Pick a vertex $v$, it has $8$ edges coming out.

Suppose $6$ of them are red, then the $K_6$ on those six vertices contains a red $K_3$ or a blue $K_3$, if there is a red $K_3$ we get a red $K_4$ after adding vertex $v$.

Suppose $4$ of them are blue, then the $K_4$ of those $4$ vertices cannot contain a blue edge, so all its edges are red, but then there is a red $K_4$.

So each vertex has exactly $5$ red edges comming out of it. Using the hadshake lemma there are $\frac{9\cdot5}{2}$ red edges, contradiction.

So $R(3,4)\leq 9$.

We now use $R(s,t)\leq R(s-1,t)+R(s,t-1)$ to get $R(4,4)\leq 2R(3,4)=18$ as desired.

• that was awesome !!! our teacher proved that $K_9$ is colored red and blue there is a red $K_4$ or a blue $K_3$ without ramsey theory. so with your proof, everything is ok :) thank you :) you've helped me in other questions, too. – Arman Malekzadeh Feb 5 '16 at 2:10
• Happy to help, tell me if something is unclear. – Yorch Feb 5 '16 at 2:18
• you can find $K_{17}$ colored red and blue with blue or red $K_4$ here – Yorch Feb 5 '16 at 2:23
• the last part, i don't want to use ramsey numbers ! can you prove that with just graph-theory? – Arman Malekzadeh Feb 5 '16 at 15:20
• yes, suppose there are $18$ vertices, pick a vertex $v$, then at least $9$ blue edges come out of $v$ or at least $9$ red edges come out of $v$. in the first case notice there is a blue $K_3$ inside the $K_9$ or a red $K_4$, if there is a blue $K_3$ it turns into a blue $K_4$ after adding the vertex $v$. The case in which there are $9$ red edges is analogous. – Yorch Feb 5 '16 at 19:36