SCHWEITZER 2005 Problem 1

Let [n] be the set {1, 2,. . . , n}.

For any $a, b \in N$ , denote $G (a, b)$ by a graph (not directed) defined by the following rule: the vertices have the form (i, f), where $i \in [a]$ , and $f: [a] \to [b]$ . A vertex (i, f) and a vertex (j, g) are connected if $i \neq j$ , and $f (k) \neq g (k)$ holds exactly for k strictly between i and j. Prove that for any $c \in N$ there is $a, b \in N$ such that the vertices of G (a, b) cannot be well-colored with $c$ colors.