If the edges of the complete graph $K_{17}$ (on 17 vertices with no three collinear) are each colored one of three colours can it be proven to have two or more monochromatic triangles?
$\begingroup$
$\endgroup$
4
asked Sep 17, 2014 at 15:16
-
$\begingroup$ It will definitely have at least $2$ monochromatic triangles. Just consider two copies of $K_6$ in the graph, and each of these copies will have a monochromatic triangle. I'm sure one could refine this simple argument to exhibit more of these triangles. $\endgroup$– zarathustraCommented Sep 17, 2014 at 15:20
-
1$\begingroup$ @FPE But three colours are being used, and so any $K_6$ subgraph potentially does as well. $\endgroup$– CasteelsCommented Sep 17, 2014 at 15:22
-
$\begingroup$ @Casteels: Sorry, misread the question. My mind only works with red and blue, are there other colours out there? $\endgroup$– zarathustraCommented Sep 17, 2014 at 15:31
-
$\begingroup$ To be fair it's related so it can work. $\endgroup$– user645636Commented Mar 6, 2019 at 18:18
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
Yes. Choose one vertex. It has sixteen edges going out, so six of some color, say yellow. Now consider the $K_6$ composed of those six vertices. If it has no yellow edges, it has two monochromatic triangles and we are done. If it has two yellow edges, we have two monochromatic triangles and are again done. If it has only one yellow edge we have one monochromatic triangle. Now choose some vertex not involved in this argument-we have only used seven, so there are ten more. It must invoke at least one monochromatic triangle by the same argument.
answered Sep 17, 2014 at 16:03
-
$\begingroup$ I can't seem to prove your Case2 (If it has two yellow edges, we have two monochromatic triangles) see the image: i.imgur.com/W46VnWy.png $\endgroup$ Commented Sep 18, 2014 at 4:35
-
$\begingroup$ Because there are yellow edges going from each vertex of thre $K_6$ to the first vertex chosen. Each yellow edge in the $K_6$ completes a triangle with two of the ones from the first vertex. $\endgroup$ Commented Sep 18, 2014 at 5:06
-
$\begingroup$ As someone taking their first Discrete Mathematics course your solution is hard for me to justify. Is it possible for you to add more detail? Some questions: How can you assume there will be 6 edges of the same color connected to the same point? $\endgroup$ Commented Sep 18, 2014 at 17:00
-
$\begingroup$ By the pigeonhole principle. With only five of each color you have fifteen total. The sixteenth will have to match one of the sets of five. $\endgroup$ Commented Sep 18, 2014 at 20:22
-
$\begingroup$ You could present this argument a bit more simply by assuming that the chosen vertex is not in a monochromatic triangle. (If every vertex is in a monochromatic triangle then you've got at least $6$ of them.) Then the $K_6$ contains no yellow edges and you're done. $\endgroup$– bofCommented Mar 4, 2017 at 12:52
$\begingroup$
$\endgroup$
Yes, Sane & Wallis have proved in 1987 that there are at least 5 (!) monochromatic triangles in the 3-edge-colored K_17: see https://doi.org/10.1017/S0004972700026733. Optimal colorings which achieve this lower bound are known, as show the results of Al Zimmermann's Programming Contest "Monochromatic Triangles".
$\begingroup$
$\endgroup$
Here's my attempt, using a result (stronger cousin as well)from a $K_6$ which Numberphile showed:
$$4\\3_\nwarrow\hspace{6 pt}\uparrow\hspace{6pt}\nearrow^5\\\hspace{-2pt}2\leftarrow1\rightarrow6$$
Imagine we have an arbitrary $K_6$ (not that I can create one properly, without rotate or turn, or using an image). If we examine it from one vertex, and do a coloring with at most 2 colors (key words there are at most), by pigeonhole principle, we have 1 color with at least 3 of the 5 connecting lines to the other vertices. Let us assume they are red ( blue being the other for consistency with the video), then we get the following(labelling is arbitrary here, graph isn't supposed to be directed):
$$4\\3_\color{red}\nwarrow\hspace{6 pt}\color{red}\uparrow\hspace{6pt}\color{red}\nearrow^5\\\hspace{-2pt}2\leftarrow1\rightarrow6$$
We then have, the following observations:
- If the connection from 3 to 4 is red we have a red triangle 1 to 3 to 4 to 1
- If the connection from 3 to 5 is red we have a red triangle 1 to 3 to 5 to 1
- If the connection from 5 to 4 is red we have a red triangle 1 to 5 to 4 to 1
This then forces a blue triangle 3 to 4 to 5 to 3. Thinking about the other connections from 1, if either is red, all other connections to it from the blue triangle vertices, will need to be blue, forcing a monochromatic $K_4$ (containing 4 monochromatic $K_3$ subgraphs). On the other hand, if they are blue, the connection between the endpoints, needs be red to stop another blue triangle.
From the above, both other connections now have both colors (works regardless if they have both blue or both red to avoid a second triangle). If a vertex, in the blue triangle, sends both 2 and 6 the color connecting them. That forces a second triangle as well. If two blue triangle vertices send blue to either vertex 2 or 6, we have a second triangle (at least). By pigeonhole principle, that means of the 3 uncolored lines connecting to either 2 or 6, two must be red. No way of selecting 2 pairs from 3 items without overlap, Therefore 1 blue triangle vertex, must give both 2 and 6 a red line, forcing a red triangle. So every $K_6$ has at least 2 monochromatic $K_3$ subgraphs. It then follows, for all higher $K_n$.
$K_{17}$ 3 color case:
For the $K_{17}$ case with 3 colors, 16 vertex connections from a vertex, we have at least 6 are forced to one color ( pigeonhole principle). This forces either a $K_6$ using the other colors, or at least 1 monochromatic triangle of the first color, There are at least 2 distinct $K_7$ in a $K_{17}$, so this happens twice. QED.