, 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 $\binom{13}{6} = 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.