prove that k-cube has $2^k$ vertices, $k$ $2^k$ $^-$ $^1$ edges and is bipartite. The k-cube is the graph whose vertices are the ordered k-tuples of 0's and 1's, two vertices being joined if and only if they differ in exactly one coordinate.
Show that the k-cube has $2^k$ vertices, $k$$2^k$$^-$$^1$ edges and is bipartite.
Note : This question is from the book "Graph Theory With Applications" written by Bondy & Murty.
Thanks in advance.
 A: There are $2$ possibilities for each of the $k$ coordinates of a vertex, so there are $2^k$ vertices in total.
Each vertex has $k$ neighbours (why?) so the sum of the degrees of all the vertices is $k2^k$. But this counts each edge twice, so...
To show that the graph is bipartite, consider the coordinate sum of a vertex. If this sum is even, what can you say about the sums for neighbouring vertices? What if the sum is odd?
A: Another way or say words to prove bipartite. (Detailed proof)
Let V1 be the set of those vertices of Qn (i.e., sequences of 0’s and 1’s of length n) with an even number of 0’s. Similarly, let V2 be the set of those vertices of Qn with an odd number of 0’s. Clearly, every vertex must have either an odd or an even number of 0’s and, hence V1, V2 partition V (Qn) into two disjoint parts.
Is it possible to have an edge xy with x, y ∈ V1? This would mean that x and y differ in exactly one position. But this would imply that if one of them has an even number of 0’s
then the other one has an odd number of 0’s (one 0 is changed to 1 or one 1 is changed to 0), so these two vertices cannot be both from V1. This is a contradiction. In the same way one proves that it is not possible to have an edge with both vertices from V2.
