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$ 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$ – zarathustra Sep 17 '14 at 15:20
  • $\begingroup$ @FPE But three colours are being used, and so any $K_6$ subgraph potentially does as well. $\endgroup$ – Casteels Sep 17 '14 at 15:22
  • $\begingroup$ @Casteels: Sorry, misread the question. My mind only works with red and blue, are there other colours out there? $\endgroup$ – zarathustra Sep 17 '14 at 15:31
  • $\begingroup$ To be fair it's related so it can work. $\endgroup$ – Roddy MacPhee Mar 6 at 18:18

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.

  • $\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$ – TechplexEngineer Sep 18 '14 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$ – Ross Millikan Sep 18 '14 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$ – TechplexEngineer Sep 18 '14 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$ – Ross Millikan Sep 18 '14 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$ – bof Mar 4 '17 at 12:52

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.