Coloring edges of $K_n$ so each vertex has $l$ edges of each color.

Question

Given $n$ for what values of $l$ can we color the edges so that each vertex $l$ edges of each color adjacent to it.

The number of colors used is clearly $\frac{n-1}{l}$

Thank you in advance.

Answer 1

I found the answer a couple of hours after posting the question:

For starters we shall need an algorithm that in mexico we call the tortilla algorithm. It does the following: Given $n$ odd vertices place them as if they where the vertices of a convex $n$-gon and give a different color to each of the edges. color a diagonal color in the color of the side that is paralel to the diagonal. This way every vertex will have exactly one edge of each of the $n$ colors, except for the color of the edge oposite to it, it shall have zero edges of this color. To fix this we can add a new vertex and join it to all of the old ones, the edge going from this new vertex to a given old vertex is going to be colored with the color that the old vertex lacked before the addition of the new vertex.

With this algorithm we can paint the edges of a complete even graph $K_n$ with $n-1$ colors so that each of its vertices has exactly one edge of each color. Now suppose we are given $k|n-1$. We can color the graph with $\frac{n-1}{k}$ colors so that each vertex has $k$ edges how? First use the previous algorithm to color it with $n-1$ colors and then partition the set of $n-1$ colors into $\frac{n-1}{k}$ sets of $k$ colors each. For each of those sets paint the edges that where in any of those colors with a new color, so that the graph now has $\frac{n-1}{k}$ different colors. Clearly this coloring satisfies the requirement since a given vertex had exactly one edge o each of the new colors. But in the new coloring what where before $k$ colors are now one. So for any given new color there are exactly $k$ edges of that color adjacent to any particular vertex. So when the graph is even $k$ can be any divisor of $n-1$.

If $n=2m+1$ is odd we first prove when $k=2$ we can do it: Place the vertices as if they where the vertices of a regular $n$-gon and label the colors $0,1,2,3\dots m-1$. For any given diagonal of the n-gon consider the two sides in which the n-gon is divided. Then consider the side which has less points, we color the diagonal with the color that corresponds to the number of points left in that side, so for example the sides are colored with color zero. It is easy to see when we do this every vertex has two edges of each color since the two diagonals of color $s$ oming out of edge $v$ can be found by going around the vertex starting from $v$ and counting $s+1$ vertices (there are two because we can go clock or counter-clock wise). Using a method similar to the even case we can use this to prove we can always do it if $k$ is a multiple of $2$.

We now prove if $n$ is odd and $k$ is odd we cannot do it by contradiction. Suppose it is possible, pick one of the colors. Then the graph which has only edges of that color has an odd amount of vertices odd degree, a contradiction.

Thus the answer is as Casteels said, if $n$ is even any divisor of $n-1$ works and if $n$ is odd any even divisor of $n-1$ works, and these are the only values for which it works.