Hola
Demuestre o encuentre un contraejemplo: El \( k \)-cubo es un grafo bipartito para todo \( k. \)
Los vértices pueden enumerarse con el conjunto:
\( V=\{(a_1,a_2,\ldots,a_n)|a_i\in \{0,1\}\} \)
Las aristas unen dos vértices si difieren en una sola componente.
Entonces si tomamos:
\( U=\{(a_1,a_2,\ldots,a_n)\in V|a_1+a_2+\ldots+a_n\quad \textrm{par}\} \)
\( W=\{(a_1,a_2,\ldots,a_n)\in V|a_1+a_2+\ldots+a_n\quad \textrm{impar}\} \)
comprueba que es una partición del conjunto de vértices que lo dota de estructura de grafo bipartito.
Saludos.
