Graph Theory

[Neospectrum]

How would one go about proving that in k17 you will always get a monochromatic k3 using 3 colors.

[gumpzilla]

Are K17 and K3 the complete graphs on 17 and 3 vertices? I'm assuming not because otherwise this seems trivial.

[blah_blah]

yes they are, no it's not trivial.

pick a vertex v, without loss of generality it has at least 6 adjacent edges of color c_1 of the form {vv1,vv2,...vv6}. If any of {v1v2,v2v3,...,v5v6} are colored c1, we're done. assume not, so that all of them get colors c2 or c3. by the friendship theorem, there is a monochromatic triangle in color c2 or c3 from {v1v2,v2v3,...,v5v6}, whence the result follows.

[Neospectrum]

The friendship theorem part is where it gets a little complicated and hazy for me maybe someone could give a bit more in depth analysis. That cleared up the first step for me by the way it was a big help.

[blah_blah]

[ QUOTE ]
The friendship theorem part is where it gets a little complicated and hazy for me maybe someone could give a bit more in depth analysis. That cleared up the first step for me by the way it was a big help.

[/ QUOTE ]

there is a proof on the wikipedia page; it's really quite a simple proof.

[jay_shark]

Here is my proof . It uses the pigeonhole principle .

Pick any vertex . There are 16 edges emanating from that vertex . From the pigeonhole principle there exists 6 edges of the same color . (16/3>=5) . Lets say it is red .

Now pick a vertex from one of the 6 edges different from the original vertex . There are 5 lines that emanate from that vertex and so 3 of them have to be the same color . Lets say it is blue . Now the endpoints of the blue edges form a triangle that must be monochromatic . Do you see why ?

[jay_shark]

I remember when I had to prepare for the Putnam contest , there was a practice problem about proving or disproving that there exists a monochromatic triangle if you have 16 edges .

[Neospectrum]

Think I am getting it. The friendship proof is very simple its just translating that principle to three colors thats whats bothering me.

[Siegmund]

The friendship proof is a two-colour result.

Perhaps what you're missing is that you started with six lines from A to B,C,D,E,F,G, all red. If any one of BC,BD,BE,BF,BG,CD,CE,CF,CG,DE,DF,DG,EF,EG,FG is red, you're done. If ALL of these are either green or blue, apply the friendship principle, assemble a green or blue triangle from these 15 segments.

Spelling it out in more detail... look at BC, BD, BE, BF, and BG. If these 5 are all either green or blue, there is a set of 3 the same colour among them. WLOG let's say that BC, BD, and BE are green.

Now, consider the lines CD, CE, and DE.
If any one of these is red, it forms a red triangle, since AC, AD, and AE are red.
If any one of these is green, it forms a green triangle, and BC, BD, and BE are green.
If all three of these is blue, CDE is a blue triangle.

[Neospectrum]

Alright I am there, thanks guys really appreciate the help. One last question is there a general statement that can be made that there exists a "best" Kn graph containing a monochromatic K3 coloring for some integer X colors. Or am I making any sense for that matter of fact?