Assume that we have a $K_{17}$ and we color every edge of it with 3 colors ( Like Red, Blue & green ).

Prove that for every coloring of $K_{17}$ with 3 colors, After coloring, We have a one-color $K_3$.

Note 1:
What i tried is that i picked and vertex like $v$ and i fixed it.
Then I said this vertex is connected to $16$ other vertices ($v_1,\cdots,v_{16})$.
By the pigeonhole principle we know that there exists a color that at least 6 of the edges between $v$ and $v_i$'s.
Without loss of generality, We say that color is blue and that 6 vertices are $(v_1,\cdots,v_6)$.
Now we see the edges between $v_i$'s. If there exists a blue edges between these vertices, We are done ! What i'm stuck on is what to do if there is no blue edge between $v_i$'s.

Note 2: Don't use ramsey numbers.

Thanks in advance.

  • 1
    $\begingroup$ If there's no blue edge between $v_i$'s then you've got a $K_6$ whose edges are colored with two colors. Have you seen anything about two-colored $K_6$'s? If you have, this is a good place to use it. If you haven't attack it the same way you did the $K_{17}$ problem: Pick one of those six vertices and look at the $5$ edges joining it to the others . . . $\endgroup$
    – bof
    Commented May 3, 2016 at 7:23
  • $\begingroup$ @bof Thank you dude :) I know that ! What a good place to use it ! I'll delete my question :) $\endgroup$ Commented May 3, 2016 at 7:24
  • $\begingroup$ @bof i'm not sure ... should i delete the question anyway ? $\endgroup$ Commented May 3, 2016 at 7:26
  • $\begingroup$ @ArmanMalekzade it's not a duplicate so there is no need to delete it, it might be helpful for other people in the future :) $\endgroup$
    – H. Potter
    Commented May 3, 2016 at 7:37
  • $\begingroup$ @H.Potter ok :) $\endgroup$ Commented May 3, 2016 at 7:38


Browse other questions tagged .