MathDB

Tricoloured Complete Graph

Source: China Team Selection Test 3 Day 2 P2

March 25, 2015

graph theorycombinatorics

Problem Statement

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)

.

Back to Problems View on AoPS