For any 3-coloring of $K_{17}$ I have to show there exists either a red, blue or green triangle. To start, can I use proof by contradiction with color red, blue, green? So $(0,0,136)$ means all 136 edges are green. Clearly this has green triangle. If we color the "outside" of the graph all one color, say red, then we have 17 edges that are red and no edge of the interior can be colored red in order to avoid red triangles. Then I try to obtain a contradiction?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Is the coloring on the vertices or edges? $\endgroup$– AsinomásCommented Jan 27, 2014 at 0:01
-
$\begingroup$ The coloring is on the edges. So one vertex can have an edge thats green, red, and blue connecting off of it. $\endgroup$– adfasdfCommented Jan 27, 2014 at 0:02
-
$\begingroup$ This also was an imo problem a long time ago:artofproblemsolving.com/Wiki/index.php/1964_IMO_Problems/… $\endgroup$– AsinomásCommented Jan 27, 2014 at 0:11
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
pick a vertex, then that vertex is connected to 16 vertices by 16 edges.
Of these 16 edges there is a color(a) that contains at least 6 of these edges. If any of the edges connecting those edges is colores a then there is a triangle in color a. So then the edges between those 6 vertices are all of one of 2 colors. pick one of those vertices. Then it is connected to 5 of the others by 5 edges, and there are at least 3 of the same color(b). If one of the edges connecting any of those 3 vertices is colored b then there is a triangle on color b. therefore the edges between those 3 vertices are all of the color remaining. But that also forms a monocromatic triangle.
This number is also known as $R(3,3,3)$. And $R(3,3)=6$. If you allowed an extra color then the complete number would be $R(3,3,3,3)$. Fore more info on this notation see ramsey number in wikipedia.
$\begingroup$
$\endgroup$
Hint: Pick a vertex $v$. Consider the $16$ edges incident with $v$. By the pigeonhole principle, $6$ of those those edges will have the same color, say red. So there are $6$ vertices joined to $v$ by red edges. If two of those vertices are joined to each other by a red edge, there's your red triangle. If not . . .
