Prove that if complete graph K_n is edge-colored with n colors, there exists a cycle with each edge different color If we have a complete graph $K_n$, and color its edges with $n$ colors, can we prove that there exists a cycle with each edge of a different color?
(The cycle can be of any length)
Thanks!
 A: In fact, if the edges of $K_n$ are colored with at least $n$ different colors, then there is a rainbow triangle (a triangle whose edges are all of different colors).
Proof by induction of $n$. The result is trivial for $n\le3$. Suppose $n\gt3$. Choose a vertex $u$ and consider the graph $K_n-u=K_{n-1}$. 
If $K_{n-1}$ has edges of at least $n-1$ different colors, then it contains a rainbow triangle by the induction hypothesis. 
On the other hand, if $K_{n-1}$ has edges of at most $n-2$ different colors, then among the colors of the edges incident with $u$ there must be at least two colors which do not occur in $K_{n-1}$. If the edges $uv$ and $uw$ have two different colors not occurring in $K_{n-1}$, then $uvw$ is a rainbow triangle.
P.S. Here's an alternative presentation, really the same argument. Call the vertices $v_1,v_2,\dots,v_n$. Let's say that a color (call it "red") occurs at a vertex $v_i$ if there is a red edge joining $v_i$ to an earlier vertex, i.e., a red edge $v_jv_i$ for some $j\lt i$. Let $N_i$ be the number of new colors occurring at $v_i$, i.e., colors which occur at $v_i$ but do not occur at any $v_j$ where $j\lt i$.
Then $N_1+N_2+\cdots+N_n\ge n$, since there are edges of at least $n$ different colors. Since $N_1=0$, we must have $N_i\gt1$ for some $i$. Finally, if two new colors occur at $v_i$, then $v_i$ is in a rainbow triangle.
A: [I don't have time to write this answer very nicely, but I hope the approach is clear.]
We use induction on $n$. For $n=3$, it is clear that there is such a cycle.
Now suppose $n=k>3$. Look at a subgraph of $K_n$ with $l$ vertices. If the the set of edges with at least one endpoint in these $l$ vertices has at most $l$ colors, the remaining $n-l$ vertices will have at least $n-l$ colors of edges between them and we can use the induction hypothesis. Now assume every set of $l$ vertices has at least $l+1$ colors of edges connected to it. Can you complete the proof from here?
