The edges of a complete graph on $1000$ vertices are colored in three colors. Prove that this graph contains a non-self-intersecting single-color cycle whose length is odd and not less than $41$.
Source: Saint Petersburg math olympiad 2024, 10.7
Tags: combinatorics
The edges of a complete graph on $1000$ vertices are colored in three colors. Prove that this graph contains a non-self-intersecting single-color cycle whose length is odd and not less than $41$.