Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

2  
What did you try? –  Did Jan 5 '13 at 19:25
1  
@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
add comment

2 Answers 2

up vote 1 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|improve this answer
add comment

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|improve this answer
add comment

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