# Is the hypercube graph $\{0,1\}^k$ bipartite? [duplicate]

Possible Duplicate:
How to find chromatic number of the hypercube $Q_n$?

Let $G$ be the graph whose vertex set is the set of $k$-tuples with coordinates in $\{0,1\}$ with $X$ adjacent to $Y$ when $X$ and $Y$ differ in exactly one position. Determine whether $G$ is bipartite.

-

## marked as duplicate by Austin Mohr, Chris Eagle, Alexander Gruber♦, Douglas S. Stones, MicahJan 6 '13 at 1:12

What did you try? – Did Jan 5 '13 at 19:25
@Austin Mohr ,The "How to find chromatic number of the hypercube $Q_{n}$?" is not my question ! – Vahid Dashad Jan 6 '13 at 10:49
Really? Did you read the answers on the other page? – Did Jan 6 '13 at 10:52

It is always bipartite.When $k=1$ your graph is an edge and let your parts be its vertices, and when $k\geq2$ Select an arbitrary vertex, then put one part $V_{1}$ vertices that differ with it in odd positions and the other part $V_{2}$ vertices which differ with it in even positions. Assume that there is an edge like $uv$ where $u$ and $v$ both are in $V_{1}$. If $u$ differ with our fixed vertex in $2k+1$ position then pay attention that because there is an edge between $u$ and $v$, $v$ differs with $u$ only in one position so it can differ with our fixed vertex in $2k$ or $2k+2$ position and should be in $V_{2}$ that is contradiction. So there isn't any edge between vertices of $V_{1}$ and by the same way you can see that there isn't any edge between vertices of $V_{2}$.