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 ?

[Neospectrum]

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

[hexag1]

MATH!!!!!!!!!!