Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
up vote 2 down vote accepted

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}$.

share|cite|improve this answer

Hint: consider the parity (i.e. if there are an odd no. of ones or an even no. of ones) of each vertex. What are the parities of a pair of adjacent vertices?

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.