Question 143
Let $n$ be a positive integer. Let $V_{n}$ be the set of all sequences of 0's and 1's of length $n$. Define $G_{n}$ to be the graph having vertex set $V_{n}$, such that two sequences are adjacent in $G_{n}$ if and only if they differ in either 1 or 2 places. For instance, if $n=3$, the sequences $(1,0,0)$, $(1,1,0)$, and $(1,1,1)$ are mutually adjacent, but $(1,0,0)$ is not adjacent to $(0,1,1)$.
Show that, if $n+1$ is not a power of $2$, then the chromatic number of $G_{n}$ is at least $n+2$.
Show that, if $n+1$ is not a power of $2$, then the chromatic number of $G_{n}$ is at least $n+2$.