Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza

An edge‐coloring of a complete graph with a set of colors C is called completely balanced if any vertex is
incident to the same number of edges of each color from C. Erdős and Tuza asked in 1993 whether for any graph F on ℓ edges and any completely balanced coloring of any sufficiently large complete graph using ℓ colors contains a rainbow copy of F . This question was restated by Erdős in his list of “Some of my favourite
problems on cycles and colourings.” We answer this question in the negative for most cliques F=K$_q$ by giving explicit constructions of respective completely balanced colorings. Further, we answer a related question concerning completely balanced colorings of complete graphs with more colors than the number of edges in the graph F .