Please prove the following theorem from Gallai :
Theorem .In every coloring of a complete graph with three colors that avoiding rainbow triangle , at least one of the color classes must be disconnected.
Please prove the following theorem from Gallai :
Theorem .In every coloring of a complete graph with three colors that avoiding rainbow triangle , at least one of the color classes must be disconnected.
("Rainbow triangle" means a triangle whose edges are colored with three different colors.)
This result goes back to a 1967 paper of Gallai. It is proved, as Lemma A, in the following paper: "Edge colorings of complete graphs without tricolored triangles", András Gyárfás, Gábor Simony, Journal of Graph Theory, 46, #3, pages 211–216, July 2004, doi: 10.1002/jgt.20001 .