# can we find a $k_4$ colored with 1 color in a $k_8$ which is colored with just 2 colors?

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 .

• What is the minimum size of a set of edges such that each $K_4$ contains at least one edge in the set? – 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$:
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.