My Math Forum (http://mymathforum.com/math-forums.php)
-   Applied Math (http://mymathforum.com/applied-math/)
-   -   Graph theory : coloring edges (http://mymathforum.com/applied-math/17163-graph-theory-coloring-edges.html)

 Nekochan January 28th, 2011 11:39 AM

Graph theory : coloring edges

Hello,
here is a "funny" problem. This is not homework and I don't need urgent answer.

Consider an integer n>1 and n colors. Take a complete graph and color the edges such that for any three distinct vertices, one color occurs exactly twice. What is the maximal possible number of vertices ?

Easily, for n=2, this is a well-known thing (due to Euler I think) that we cannot color a 6-vertices complete graph with 2 colors without having a monochromatic triangle, so the answer is 5 when n=2.
But even for n=3 this seems complicated. It is not difficult to see that n cannot be greater than 15, since if there are at least 16 vertices for 3 colors, then there is a color such that a vertex x is connected with at least 6 edges colored in the same way, and the 6 vertices of these edges form a complete graph colored with 2 colors, which is impossible.

So far, this "proof" can be used to find an upper bound, but I have not obtained anything else on the problem. Could anyone tell me if this problem is known, solved, or have an idea to get additional result? Thanks by advance

 All times are GMT -8. The time now is 10:42 PM.