Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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?

share|improve this answer
    
I'm coloring vertices and not edges. Or am I missing something? –  userJD-512 May 9 '11 at 19:21
    
@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. –  El'endia Starman May 9 '11 at 20:12
    
thanks –  userJD-512 May 9 '11 at 20:18
    
@userJD-512: You're welcome. :) –  El'endia Starman May 9 '11 at 20:54
add comment

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.

share|improve this answer
    
You should use the pigeonhole principle here. –  Dennis Gulko May 9 '11 at 18:07
3  
$n>4$? Because if I color the vertices {1,2,3,4} (clockwise, for example) red:{1,2} and blue:{3,4}, there's no monochromatic triangle. –  userJD-512 May 9 '11 at 18:08
    
@userJD-512: Thanks, I corrected my post. –  Dennis Gulko May 9 '11 at 20:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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