Problem

Source: China Team Selection Test 3 Day 2 P2

Tags: graph theory, combinatorics



Let $G$ be the complete graph on $2015$ vertices. Each edge of $G$ is dyed red, blue or white. For a subset $V$ of vertices of $G$, and a pair of vertices $(u,v)$, define \[ L(u,v) = \{ u,v \} \cup \{ w | w \in V \ni \triangle{uvw} \text{ has exactly 2 red sides} \}\]Prove that, for any choice of $V$, there exist at least $120$ distinct values of $L(u,v)$.