How many colours to connect cliques?

Abstract

We study the following problem: given an edge-colouring of a $K_n$ with $r$ colours, how many colours does one need to keep (in the worst-case scenario) so that the subgraph formed by those colours is connected? We determine this extremal function up to constant factors in every parameter regime, and show that it has the same asymptotic order as the corresponding number (of colours) needed for ensuring that no vertex is isolated. This gives a complete description of the ``spanning'' threshold for connectivity in edge-coloured complete graphs.