MathDB

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

. 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.

Problem Statement