An anti-Ramsey theorem (Q5917511)

The Turán number \(t_p(n)\) is the maximum size of a graph with \(n\) vertices without subgraphs isomorphic to the complete graph \(K_p\). A subgraph of \(K_n\) is called totally multicoloured (with respect to an edge colouring of \(K_n\)) if all edges have different colours. Let \(h_r(n)\) be the minimum number of colours so that any edge colouring of \(K_n\) with exactly that many colours produces at least one totally multicoloured copy of \(K_r\). \textit{P. Erdős}, \textit{M. Simonovits} and \textit{V. T. Sós} [Coll. Math. Soc. János Bolyai 10, 633--643 (1975; Zbl 0316.05111)] proved the existence of a number \(n_0(p)\) so that \(h_{p+1}(n)=t_p(n)+2\) for \(n>n_0(p)\). The present authors prove \(h_{p+1}(n)=t_p(n)+2\) for \(3\leq p<n\).