Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

("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 .

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.