We've colored edges of $K_n$ with $n-1$ colors. We call a vertex rainbow if it's connected to all of the colors. At most how many rainbows can exist? Proposed by Morteza Saghafian
Problem
Source: Iran 3rd round 2012-Combinatorics exam-P1
Tags: algorithm, combinatorics proposed, combinatorics
24.09.2012 20:05
The answer is $n$ for $n$ even and $n - 1$ for $n$ odd. We prove by induction. First, notice that it is not possible for $K_n$ to have $n$ rainbows if $n$ is odd; since each edge of a particular color joins two vertices, and there are no repeats, some vertex does not have an edge of that color, meaning it is not a rainbow. Also, if we establish the result for even $n$, the odd case follows immediately; just take $K_{n - 1}$ where all vertices are rainbows and join to it an $n^{th}$ vertex all of whose edges are some new $n^{th}$ color. Consider $n$ even. If $4 | n$, we can simply draw $2$ copies of a rainbow $K_{\frac{n}{2}}$ and join them by $K_{\frac{n}{2}, \frac{n}{2}}$ which cycles through the other $\frac{n}{2}$ colors so that every vertex is a rainbow. Then suppose $2 || n$. Label the vertices $v_1, v_2, \dots, v_{4k + 2}$ with indices considered modulo $n$, and the colors $c_1, c_1, c_2, \dots, c_{4k + 2}$. The following algorithm gives a rainbow coloring of each vertex: Color with color $c_{2i}$ edge $v_{2i + 1}v_{2i + 2}$ and all edges of the form $v_{2i + 1 - (2j + 1)}v_{(2i + 2) + (2j + 2)}$ and $v_{(2i + 1) - (2j + 2)}v_{(2i + 2) + (2j + 1)}$ where $j$ varies from $0$ to $k - 1$ and $i$ from $0$ to $2k + 1$. This colors all even-length edges in a way that every vertex is incident on exactly one of them. Now consider the set of odd length edges, that is, those edges of length $t$ where $t$ is odd. If we repeatedly move clockwise starting at $v_1$ along an edge of length $t$, we will return to our original position after an even number of moves. We can take every other edge we have traversed and color it with the color $c_t$ and color the remaining half of the edges with the color $c_{n - t}$. If we do this for $v_1$ through $v_{t}$ we will ensure that every vertex is incident on an edge of color $c_t$ and color $c_{n - t}$ exactly once each.
16.04.2017 15:29
$n$ is even. Take a subgraph $K_{n-1}$ without the vertex $v$.Now $\forall c\in K_{n-1}$ label it with a number from $0$ to $n-2$.To the edge connecting $i-j$ we give color $i+j_{n-1}$.Of course this implies that all edges incident to $i$ have different colors as $i+m=i+n$ for $m\not = n$ in $\mathbb{Z}_{n-1}$.Note that in the previous construction the vertex with label $i$ is missing an edge of colour $2i$ and $n-1$ is odd map $i\mapsto 2i$ is injective and so we can simply label the edge $i-v$ with colour $2i$. $n$ is odd. Notice that if the whole graph would be rinbows each edge would appear equal number of times but $\frac{1}{n-1}\cdot \binom{n}{2}\not \in \mathbb{N}$ so that fails.Now just pick a subgraph $K_{n-1}$ and repeat the procedure for even $n$