Need solution

Question 2 The a hypercube of dimension n is a graph Hn = (V, E), where V = {0, 1}". Le., each vertex is an n-bit string. There is an edge between two vertices u1 ... Un and v1 . .. Un, if and only if the vertex labels differ in exactly one bit, i.e., there is exactly one index i c {1, ..., n} such that wi * vi. The following depicts H3, the hypercube of dimension 3. 111 101 110 11 100 001 010 000 Observe that each node v1 . . . Un in Hn has exactly n neighbours (each neighbour can be reached by flipping exactly one of the bits v1, . . ., Un). We now define the directed hypercube Dn of dimension n as follows: The vertex set of Dn is also {0, 1}". There is an edge from u1 ... Un to v1 . .. Un, if and only if the two nodes are neighbours in Hn, and v1 ... Un contains more Is than uj . . . Un. (a) Draw D3, the directed hypercube of dimension 3. (b) Suppose the string v1 . .. Un contains exactly k Os. How many outgoing and how many ingoing edges does vertex v1 . . . Un of Dn have? Explain. (c) Using your answer to (b), prove that M