Any idea on this problem? I think using probability, especially 'Lovász local lemma' might be helpful. But I was not able to make up complete proof yet.

Solution:

Attachments:

Any idea for a probabilistic solution? (Perhaps using Lovasz' Local Lemma?)

I would like to note that the solution of SinaQane (probably the official one) has many common ideas with the solution of ISL 2015 C7 (again proposed by Russia). Indeed, the idea here is to construct too many "colorful" cycles, which pass through a special edge (in this case $ab$, where $b$ has the color, appearing minimal number of times and $a$ is constructed using the maximality of $k-colorable$ subgraph.). However, the algorithm for construction of these cycles for each subset of colors is the same as the one in the ISL problem.

SinaQane wrote: Solution:

Stupid question (just to have sure that I've been solving the right problem)

SinaQane wrote: Solution: in final part found [e(k-1)! -1] cycles pass through a vertex ,but problem gives a bound for cycles through edges , is this really a contradiction?