Problem

Source: ELMO Shortlist 2024/C3

Tags: Elmo, combinatorics



Let $n$ and $k$ be positive integers and $G$ be a complete graph on $n$ vertices. Each edge of $G$ is colored one of $k$ colors such that every triangle consists of either three edges of the same color or three edges of three different colors. Furthermore, there exist two different-colored edges. Prove that $n\le(k-1)^2$. Linus Tang