3
$\begingroup$

Looking for some hints on a homework problem. As far as I know, it's not from any textbook.

Color the vertices of $K_n$, the complete graph on $n$ vertices, red or blue. For how many $n$ will there be no monochromatic triangles (vertices all the same color). Note this question is not the one about coloring the edges.

My conjecture: for $n\ge 5$, there will always be a red or blue triangle.

I'm hoping the "pigeonhole principle" will apply somewhere. I don't think the instructor is asking us to delve into Ramsey theory.

Thanks in advance.

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

In the case that edges are irrelevant:

Your conjecture is completely correct. Here's how to apply the pigeonhole principle: with four vertices, there may be two of both colors. However, when you add a fifth vertex, it must be either red or blue, which forms a triangle with the other two of the same color. Another way to ask the same kind of question is how many integers does one need to have in order to have three even numbers or three odd numbers?

In the case that edges are relevant:

Your conjecture is almost correct. You can color the outside 5 lines forming a regular pentagon blue and the inner 5 lines (a star) red and yet not have a monochromatic triangle. However, it is true that for $K_n$ with $n \geq 6$ a monochromatic triangle WILL be forced.

Step 1: Take a vertex on $K_6$ and note that at least half of the lines from it must be one color or another. Now color three lines from it either color (say, blue).

Step 2: Apply pigeonhole principle; between the other vertices connected by a blue line to the first one, can the lines be blue or red?

Does that suffice?

$\endgroup$
2
  • $\begingroup$ I'm coloring vertices and not edges. Or am I missing something? $\endgroup$
    – userJD-512
    Commented May 9, 2011 at 19:21
  • $\begingroup$ @userJD-512: Well, in order to have a monochromatic triangle, one must have 3 edges of the same color, yes? It's possible that your instructor may be considering edges to be irrelevant, in which case your conjecture is correct is as stated. I'll edit my answer to reflect both cases. $\endgroup$
    – El'endia Starman
    Commented May 9, 2011 at 20:12
4
$\begingroup$

Since all vertices are connected, it's sufficient to show that there are 3 vertices with the same color. Since you are coloring with two colors, for all $n > 4$ there will be three vertices with the same color.

$\endgroup$
3
  • $\begingroup$ You should use the pigeonhole principle here. $\endgroup$
    – Dennis Gulko
    Commented May 9, 2011 at 18:07
  • $\begingroup$ you should work on edges not vertices. $\endgroup$
    – Mosab Shaheen
    Commented Sep 1, 2018 at 11:44
  • $\begingroup$ for n=5 i.e. pentagon you can draw edges without a triangle of same color $\endgroup$
    – Mosab Shaheen
    Commented Sep 1, 2018 at 11:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .