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.

prove $n$-cube is a bipartite graph for all $n\ge1$

This is a problem in my textbook and I cannot figure it out at all and have a test on graph theory tomorrow any help would be appreciated since I am not very good with proofs

share|improve this question
3  
The vertices of the $n$-cube are the points $\{0,1\}^{n}$; two vertices are joined by an edge only if they differ in exactly coordinate, which means that the sums of their coordinates ($0 \le \sum_{i} x_i \le n$) differ by exactly $1$. Look at the parity of this sum. –  mjqxxxx Feb 12 '13 at 21:07
    
See also math.stackexchange.com/a/227689/1543 –  Willie Wong Feb 13 '13 at 12:04
add comment

3 Answers

When labeling your $n$-cube, you can assign the vertices strings of length $n$ from $(00..0)$ to $(11..1)$. For example a $2$-cube (or square) would be: $$00\ 01\\10\ 11$$ Now you can define two subesets of your graph $G= (X,Y)$. Where $X=${vertices who have an even number of $1$'s} and $Y=${vetices who have an odd number of $1$'s}.

By creating an edges {$1,0$} or {$0,1$} starting in $X$ and ending in $Y$ all edges are accounted for and therefore, the graph is bipartite.

share|improve this answer
add comment

Hint: If a graph is bipartite, it means that you can color the vertices such that every black vertex is connected to a white vertex and vice versa.

Hint: Consider parity of the sum of coordinates.

share|improve this answer
add comment

The vertices of the $n$-cube are vectors $(v_1,v_2,\ldots,v_n)$ with entries $v_i\in\{0,1\}$. Two vertices are adjacent if and only if their representing vectors differ in exactly one entry.

Now partition the vertex set into two subsets, consisting of all vertices whose representing vector has an even (resp. odd) number of $1$'s. This partition gives a bipartite graph.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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