How many minimal proper edge colorings of $K_n$ are there? A minimal proper edge coloring of a complete graph is a coloring of $K_{2n}$ with $2n-1$ colors or $K_{2n-1}$ with $2n-1$ colors are there such that each vertex is incident with at most one edge of each color.

I'm not entirely sure how to define unique, but I think that two edge colorings are the same if you can permute the colors and vertices of one colored graph to get the other.

I suspect that the answer is $1$ for $K_{2n}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.