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

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|cite|improve this question
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 – Willie Wong Feb 13 '13 at 12:04

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|cite|improve this answer

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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.