¿Es el grafo del hipercubo $\{0,1\}^k$ bipartito?

Question

Possible Duplicate:
¿Cómo encontrar el número cromático del hipercubo $Q_n$?

Sea $G$ el grafo cuyo conjunto de vértices es el conjunto de $k$-tuplas con coordenadas en $\{0,1\}$ con $X$ adyacente a $Y$ cuando $X$ y $Y$ difieren en exactamente una posición. Determine si $G$ es bipartito.

Answer 1

Pista: considera la paridad (es decir, si hay un número impar de unos o un número par de unos) de cada vértice. ¿Cuáles son las paridades de un par de vértices adyacentes?

Answer 2

Siempre es bipartito. Cuando $k=1$, tu gráfico es solo una arista y deja que tus partes sean sus vértices, y cuando $k\geq2$, selecciona un vértice arbitrario, luego coloca un conjunto de vértices $V_{1}$ que difieren con él en posiciones impares y el otro conjunto de vértices $V_{2}$ que difieren con él en posiciones pares. Supongamos que hay una arista como $uv$ donde tanto $u$ como $v$ están en $V_{1}$. Si $u$ difiere con nuestro vértice fijo en la posición $2k+1$, presta atención porque hay una arista entre $u$ y $v$, $v$ solo difiere de $u$ en una posición por lo que puede diferir con nuestro vértice fijo en la posición $2k$ o $2k+2$ y debería estar en $V_{2}$, lo cual es una contradicción. Por lo tanto, no hay ninguna arista entre los vértices de $V_{1}$ y de la misma manera se puede ver que no hay ninguna arista entre los vértices de $V_{2}$.