A Ramsey Application

[jay_shark]

A graph has 9 points . Each edge is colored red or blue . Every triangle has a red edge . Show that there are 4 points with all edges between them all red .


I know that for any 6 points there must be a red triangle . This is a simple application of the pigeonhole principle. Somehow , I have to show that there exists a vertex with 6 red edges to the 8 remaining points . If I can show this , then I've solved the problem .

[arahant]

Just to make sure you didn't leave anything out before I play with it (though someone will answer you before I even GET to the problem /images/graemlins/smile.gif )....Can I assume this is a complete graph, since if it isn't it's trivialy false?

Or was I supposed to assume that from the title..

[jay_shark]

Yes it's a complete graph . All edges are connected so there are 9c2 edges in total .

I know that there must be two distinct red triangles . I also know that if I can find a vertex with 6 red segments , then the problem is solved .

As a follow up question . Can you have 14 distinct blue line segments so that there isn't an all blue triangle ? If so , then my contradiction attempt has failed .

[jay_shark]

Pick any point , lets call it a1 . If there are 4 blue segments connecting a1 with ai for i=2 to 9 , then we are done . The only way this may be possible is if for every vertex , there are exactly 3 blue connecting segments .

If one vertex contains only two blue segments then we're done . The reason is because there must be 6 red segments connecting the 6 points to one of the ai's but then there must be a red triangle within the 6 points .

The question now becomes ; Is it possible for every vertex to connect exactly 3 blue segments to the remaining points?

Suppose it's true . Then the number of distinct blue segments is 3*9/2=13.5 which is a contradiction since we cannot have exactly 13.5 blue line segments . Think about it this way , if it were possible then for every vertex there are exactly 3 blue segments which is 3*9 . However , every blue segment is counted twice so we have to divide by two .

It is also interesting to note that it's possible to have 8 points such that there are no 4 points with the edges all red . Arrange 8 points on the circumference of a circle and color the two neighbouring segments and the two points adjacent to its neighbours . If you draw the picture , you can see immediately that it's possible .

[thylacine]

[ QUOTE ]
Pick any point , lets call it a1 . If there are 4 blue segments connecting a1 with ai for i=2 to 9 , then we are done . The only way this may be possible is if for every vertex , there are exactly 3 blue connecting segments .

If one vertex contains only two blue segments then we're done . The reason is because there must be 6 red segments connecting the 6 points to one of the ai's but then there must be a red triangle within the 6 points .

The question now becomes ; Is it possible for every vertex to connect exactly 3 blue segments to the remaining points?

Suppose it's true . Then the number of distinct blue segments is 3*9/2=13.5 which is a contradiction since we cannot have exactly 13.5 blue line segments . Think about it this way , if it were possible then for every vertex there are exactly 3 blue segments which is 3*9 . However , every blue segment is counted twice so we have to divide by two .

It is also interesting to note that it's possible to have 8 points such that there are no 4 points with the edges all red . Arrange 8 points on the circumference of a circle and color the two neighbouring segments and the two points adjacent to its neighbours . If you draw the picture , you can see immediately that it's possible .

[/ QUOTE ]

Just skimmed, but looks good. /images/graemlins/smile.gif

[jay_shark]

Thanks , it was actually harder than I thought .
It took me a little less than 24 hours to figure it out :P