[Math] Prove that if complete graph K_n is edge-colored with n colors, there exists a cycle with each edge different color

graph theory

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!

Best Answer

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.

Related Question