Assume that we define edge coloring in this way :
An edge coloring of a graph is an assignment of "colors" to the edges of the graph.
So, now imagine we have a $K_8$ which has edges colored with just 2 colors ( for example, red and blue )
Can we find a $k_4$ which is colored with just 1 color?
Note : In our class , teacher proved this for $k_6$ and $k_3$ . i mean that we have a $k_3$ with just 1 color in a $k_6$ that is colored with 2 colors. now i'm not sure about this one. so, if it's correct , please provide a proof. if it's not, please prove that too .
Thanks in advance.

  • $\begingroup$ What is the minimum size of a set of edges such that each $K_4$ contains at least one edge in the set? $\endgroup$ – deinst Jan 31 '16 at 17:53

What you want to prove is that the ramsey number $R(4,4)$ is less than or equal to $8$.

This is false, we know that $R_{4,4}$ is in fact $18$.

Here is a simple counterexample for $K_8$:

enter image description here

To see why it is a counterexample notice if we pick $4$ vertices at least $2$ vertices will be distance $3$ or more apart, so at least one red edge, on the other hand, there will also be two vertices will be distance $1$ or $2$ apart, so at least one blue edge.

  • 1
    $\begingroup$ thank you dude :) today was our first Combinatorics class and i'm a newbie at ramsey theory ! but i found it so cool ! $\endgroup$ – Arman Malekzadeh Jan 31 '16 at 18:05
  • $\begingroup$ You're welcome, happy to help. $\endgroup$ – Jorge Fernández Hidalgo Jan 31 '16 at 18:06

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.