This is a repost of [this](https://math.stackexchange.com/questions/458780/probability-that-a-random-edge-coloring-of-the-complete-graph-is-proper) math.se question that I am posting here since it received no attention there. 



> 
> What is the probability that a random edge coloring of $K\_n$ with 
>  $m \geq n$ colors results in a proper coloring ?
> 
> 
> 


By random edge coloring I mean that every edge is assigned a color from $\{1,\ldots,m\}$ uniformly at random. 


If we define the event $E\_i$ to mean that edge $e\_i$ is not incident with an edge of the same color class of the event $V\_i$ that vertex $v\_i$ is incident with edges of distinct colors, then it is easy to get a bound for the above probabiity in terms of $Pr[E\_i]$ or $Pr[V\_i]$ by using the union bound.


The problem is that it appears that such approach only gives bounds that make sense only when $m = \mathcal(n^2)$ which is not interesting.


Hence I am wondering if there is a more sensitive way to bound/compute the above probability?



Probability that a random edge coloring of the complete graph is proper
Let $p(n)$ be this probability. Now consider you coloured $K\_{n-1}$ successfully and add one new vertex. As the edges from the new vertex is coloured, there are simple bounds on how many colours are available. I get that the $i$-th new edge ($i$ starting at 0) has between $m-n+2-i$ and $m-n+2$ colours available. Therefore
$$ \frac {(m-n+2)!}{m^{n-1} (m-2n+3)!} \le \frac{p(n)}{p(n-1)} \le \frac{(m-n+2)^{n-1}}{m^{n-1}}.$$
Multiply these ratios together to bound $p(n)$. The left bound starts to bite when $m\ge 2n-3$, the right bound earlier.


I'm sure this can be improved.


