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.

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

  • $\begingroup$ 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. $\endgroup$ – Arman Malekzadeh Feb 5 '16 at 2:10
  • $\begingroup$ Happy to help, tell me if something is unclear. $\endgroup$ – Yorch Feb 5 '16 at 2:18
  • $\begingroup$ you can find $K_{17}$ colored red and blue with blue or red $K_4$ here $\endgroup$ – Yorch Feb 5 '16 at 2:23
  • $\begingroup$ the last part, i don't want to use ramsey numbers ! can you prove that with just graph-theory? $\endgroup$ – Arman Malekzadeh Feb 5 '16 at 15:20
  • $\begingroup$ 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. $\endgroup$ – Yorch Feb 5 '16 at 19:36

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.