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}{w|wVuvw has exactly 2 red sides}Prove that, for any choice of V, there exist at least 120 distinct values of L(u,v).