In [Er91] Erdős credits this problem to himself, Pyber, and Tuza. This problem was explored in a paper of Erdős and Tuza [ErTu93]. In [Er96] Erdős seems to suggest that this might be true for every graph $G$, and specifically asks specific challenge posed in [Er91] and [Er96] is whether, in any balanced edge-colouring of $K_{6n+1}$ by $6$ colours there must exist a rainbow $C_6$ and $K_4$.

In general, one can ask for a quantitative version, defining $d_G(n)$ to be minimal (if it exists) such that if $n$ is sufficiently large and the edges of $K_n$ are coloured with $e(G)$ many colours such that the minimum degree of each colour class is $\geq d_G(n)$ then there is a rainbow copy of $G$. Erdős and Tuza [ErTu93] proved that\[\lfloor n/6\rfloor \leq d_{C_4}(n) \leq \left(\frac{1}{4}-c\right)n\]for some constant $c>0$.

Axenovich and Clemen [AxCl24] have proved that there exist infinitely many graphs without this property. In particular, they show that for any odd $\ell \geq 3$ and $m=\lfloor \sqrt{\ell}+3.5\rfloor$ there exist arbitrarily large $n$ such that $K_n$ has a balanced edge-colouring using $\ell$ colours which contains no rainbow $K_m$. They conjecture that $K_m$ lacks this property for all $m\geq 4$.

Clemen and Wagner [ClWa23] proved that $K_4$ does lack this property.

View the LaTeX source

This page was last edited 14 October 2025.