Is minimum colors needed to assign colors to edges of complete graph $K\_n$ so that every even simple cycle contains an odd number ($>1$) of colors much larger than $(\log n)^\beta$ or $n^{\frac{1}\beta}$ with some fixed $\beta>1$?


What is a good upper bound?



Minimal edge color on constraints
Yes.


Suppose that we did this with $k>1$ colors. For any pair of colors, the graph consisting of edges with these two colors obviously does not contain any even cycle. An even cycle free graph has at most $3(n-1)/2$ edges (see <https://math.stackexchange.com/questions/438853/prove-that-the-maximum-number-of-edges-in-a-graph-with-no-even-cycles-is-floor3> ). Then add up these inequalities for any pair of colors, and observe that we counted every edge of $K\_n$ exactly $k-1$ times.


$$ \binom{n}{2} (k-1) \leq \binom{k}{2}3(n-1)/2 $$
Thus ignoring constants we have that
$$ n^2k \leq k^2 n $$
$$ n \leq k. $$
Note that $k\leq 3(n-1)/2$ also holds, as if there were more than this amount of colors, we could take an edge from any color, and the resulting graph would have an even cycle, obviously with an even number of colors. Thus roughly we have the bounds 


$$ \frac{2}{3}n \leq k \leq \frac{3}{2} n. $$


