Team Selection Test for EGMO 2024

Answer: $k=7$.

Let us show that 7 colours are sufficient. Indeed, let us randomly divide 13 colours to two groups $A$ and $B$, consisting of 7 and 6 colours, respectively. Assume that by using edges coloured to colours of group $A$ some vertex $X$ is not connected to some other vertex $Y$. It means that the edge $(X,Y)$ (the edge between $X$ and $Y$) is coloured to some colour of group $B$ and also for any other vertex $Z$, at least one of the edges $(Z,X)$ and $(Z,Y)$ is coloured to some colour of group $B$. Therefore, any two vertices of $K_{2024}$ are connected by path with edges coloured to colours of $B$. Done.

Note that the groups $A$ and $B$ may have any other sizes: It is well known that if the edges of a complete graph are coloured by two colours then the graph is connected by at least one of these colours.

Now we give an example to show that 6 colours is not enough for guaranteeing connectedness. There are $\left(\genfrac{}{}{0ex}{}{13}{6}\right)=1716$ possible choices of 6 colours. To each of these choices we assign a vertex so that for different choices assigned vertices are also different. Since $1716<2024$ such one-to-one correspondence is possible. We will colour graph edges such that for each choice of 6 colours all edges incident to the vertex assigned to these 6 colours will be coloured to one of the remaining 7 colours. Such colouring is possible: since $7+7>13$, for any two vertices their allowed 7 colours have non-empty intersection and consequently the colour of the edge connecting these two vertices can be properly chosen. By construction for any choice of 6 colours the vertex assigned to this choice is not connected to other vertices by chosen 6 colours. We are done.