# Number of distinct proper minimal edge colorings of a labeled complete graph

It seems like the answer to this question ought to be well-known, or at least some conjectures made if it's unsolved, but my searches so far have come up empty.

In how many ways may we color the edges of a labeled $K_n$, using the minimal number of colors, so that no vertex is incident to two edges with the same color?

For $K_2$, there is obviously 1: For $K_3$, we have 6: And for $K_4$, also 6: This question is related to Number of different minimal proper edge colorings of $K_n$, which currently has no answers and does not assume that the vertices are labeled.

Counting edge-colorings of $K_n$ is closely related to counting symmetric Latin squares. In fact, I'll show that if $S_n$ denotes the number of symmetric $n \times n$ Latin squares (symmetric matrices with entries in the set $\{1,2,\dots,n-1\}$ where each row and each column includes every value exactly once) then the number of minimal proper edge-colorings of $K_n$ is equal to $S_{n-1}$ when $n$ is even and $S_n$ when $n$ is odd.

This paper shows that $S_n$, the number of symmetric $n \times n$ Latin squares, satisfies $$S_n \sim n! \cdot n^{\frac38 n^2}$$ for odd $n$, which gives at least an asymptotic answer to your question as well.

When $n$ is odd, a minimal proper edge-coloring of $K_n$ uses $n$ colors, each appearing on $\frac{n-1}{2}$ edges, and therefore at each vertex one color is left out. We define a map from these edge-colorings to $n \times n$ symmetric Latin squares as follows:

• Assign values $1, 2, \dots, n$ to the colors.
• For $1 \le i < j \le n$, put the color of the edge between $i$ and $j$ in the $(i,j)^{\text{th}}$ entry of the Latin square.
• For $1 \le i \le n$, put the color not appearing at vertex $i$ in the $(i,i)^{\text{th}}$ entry of the Latin square.

The result is a symmetric Latin square, and reversing this process always produces a minimal proper edge-coloring. So the number of colorings is $S_n$.

For even $n$, we may simply reduce to the $(n-1)$-vertex case by leaving out one vertex. The resulting coloring is always a minimal proper edge-coloring of $K_{n-1}$, and we can always infer what the colors on the deleted edges must have been, and reverse this process. So the number of colorings is $S_{n-1}$.