- **Applied Math**
(*http://mymathforum.com/applied-math/*)

- - **Graph theory : coloring edges**
(*http://mymathforum.com/applied-math/17163-graph-theory-coloring-edges.html*)

Graph theory : coloring edgesHello, 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. |

Copyright © 2019 My Math Forum. All rights reserved.