Proving $R(3,3,3)\le17$

5.5k Views Asked by At

I've been working on some problems in my introductory discrete mathematics course, and I am trying to figure out a proof that $R(3,3,3) \leq 17.$ I initially consider an instance where we have a $K_{17}$ colored in the arbitrary colors $c_1,c_2,c_3$. Consider a vertex $v \in K_{17}.$ It should have 16 edges coming out of it, so by the pigeonhole principle, it should have 6 edges coming out of it that are colored in one color. Without loss of generality, we can say that these are colored $c_1$. Consider these $c_1$ adjacent vertices $v_1,...,v_6$. If there is a $c_1$ colored edge between any one of them, we are done. Otherwise, I am not entirely sure what I can do with 6 vertices whose colors are arbitrary colored $c_2$ or $c_3$. Any recommendations for this problem?