Câu hỏi 143
Cho $n$ là một số nguyên dương. Gọi $V_{n}$ là tập tất cả các dãy gồm các số $0$ và $1$ có độ dài $n$. Định nghĩa $G_{n}$ là đồ thị có tập đỉnh là $V_{n}$, trong đó hai dãy kề nhau trong $G_{n}$ khi và chỉ khi chúng khác nhau ở đúng $1$ hoặc đúng $2$ vị trí. Chẳng hạn, nếu $n=3$ thì các dãy $(1,0,0)$, $(1,1,0)$ và $(1,1,1)$ đôi một kề nhau, nhưng $(1,0,0)$ không kề với $(0,1,1)$.
Chứng minh rằng, nếu $n+1$ không phải là một lũy thừa của $2$ thì số sắc độ của $G_{n}$ ít nhất là $n+2$.
Chứng minh rằng, nếu $n+1$ không phải là một lũy thừa của $2$ thì số sắc độ của $G_{n}$ ít nhất là $n+2$.