January 28th, 2011, 11:39 AM  #1 
Newbie Joined: Jan 2011 Posts: 1 Thanks: 0  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 wellknown thing (due to Euler I think) that we cannot color a 6vertices 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 

Tags 
coloring, edges, graph, theory 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Graph theory: Linking graph characteristics and minimal cut  avnerg  Applied Math  0  September 18th, 2013 06:03 AM 
bipartite graph, vertices, edges and arithmetics  discretemath  Applied Math  1  October 27th, 2012 08:10 PM 
Proof: inequality involving vertices and edges of a graph  restin84  Applied Math  4  April 4th, 2012 12:12 PM 
Graph with nonintersecting edges  tolmachevroman  Applied Math  1  June 1st, 2011 05:00 AM 
quantity of edges if graph kregular?  viktord  Computer Science  3  May 2nd, 2009 01:13 PM 