Coloring the edges of a complete graph such that no two edges of the same color cross Need to color the edges of $K_n$ such that no two edges of the same color cross. Show that at least $\frac{n}{6}$ colors are needed. Show that this is doable with at most $\frac{n}{2}$ colors.
Any help is appreciated.
$[$ My idea was to draw $K_n$ as a regular $n$-gon. Number the vertices $1, \ldots, n$. Start from $1$, and draw all possible diagonal from $1$, color them with the same color. Keep doing this up to $\frac{n}{2}$ (and for odd $n$, $\frac{n+1}{2}$) with a new color each time. So now we have exhausted all the diagonals and no two crossing diagonals have the same color. Color the sides of the $n$-gon with any of the $n/2$ colors. This only shows that the required coloring is possible with $n/2$ colors. $]$
 A: *

*To prove that $n/6$ colors are necessary, take a coloring of $K_n$ with fewer than $n/6$ colors and consider the color $C$ which appears on the most edges. There are at least $\frac{n(n-1)/2}{n/6}=3n-3$ edges colored $C$. Now, use the fact that any planar graph with $n$ vertices has at most $3n-6$ edges to conclude  there must be two $C$ edges which cross. 

*I think your method does not work. If you stop at $n/2$ colors, you will not have colored all the edges. If you are going to use $n/2$, then on average there will be $n-1$ edges in each color, so a simple method may involve using exactly $n-1$ edges in each color. I believe the following method works for even $n$. Number the vertices $1$ to $n$. For each $v$ in $1,2,\dots,n/2$, take the following path$$(v,v+1,v-1,v+2,v-2,\dots,v+(\tfrac{n}2-1),v-(\tfrac{n}2-1),v+\tfrac{n}2)$$and color each of the edges in that path the same color. All addition is modulo $n$, so it wraps around the circle. Each color is a "zig-zag" through all $n$ vertices. Here is an example for $n=8$. (Both graphs are the same, one is colorblind friendly).

