SCHWEITZER 1997 Problem 1

Define a class of graphs $G_k$ for each positive integer k as follows. A graph G = ( V , E ) is an element of $G_k$ if and only if there exists an edge coloring $\psi: E\to [ k ] = \{1,2, ..., k\}$ such that for all vertex coloring $\phi: V\to [ k ]$ there exist an edge e = { x , y } such that $\phi ( x ) = \phi( y ) = \psi( e )$ . Prove that there exist $c_1< c_2$ positive constants with the following two properties: (i) each graph in $G_k$ has at least $c_1 k^2$ vertices; (ii) there is a graph in $G_k$ which has at most $c_2 k^2$ vertices.