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