When will the complement of a hypercube be bipartite?

Question

I know that every hyper cube is bipartite, but I am lost when it comes to their complements... I'm try to go off the theorem that "A graph is bipartite if and only if it does not contain any odd cycles", but I am having a hard time visualizing exactly when a hyper cube has odd cycles. Any hints to tackle this would be appreciated.

Answer 1

The vertices $(\color{red}{0,0,0},0,\cdots)$, $(\color{red}{1,1,0},0,\cdots)$,$(\color{red}{1,0,1},0,\cdots)$ will form a $3-$cycle.

Answer 2

The question is, for which values of $n$ the graph $\overline Q_n$, the complement of the cube $Q_n,$
is $2$-colorable (i.e., bipartite).

You know that $Q_n$ is $2$-colorable and has $2^n$ vertices. In a proper $2$-coloring of $Q_n,$ there are $2^{n-1}$ vertices of each color. The $2^{n-1}$ vertices of one color form a clique in the complementary graph $\overline Q_n,$ so $\chi(\overline Q_n)\ge2^{n-1}.$ Therefore $\overline Q_n$ is not $2$-colorable when $n\ge3.$

In fact, it is quite easy to see that $\chi(\overline Q_n)=2^{n-1}$ for all $n\ge1,$ whence $\overline Q_n$ is $2$-colorable if and only if $n\le2.$