Let n be a positive integer. The n-cube is a graph, denoted Qn, whose vertices are the 2

Chapter 52, Problem 52.13

(choose chapter or problem)

Let n be a positive integer. The n-cube is a graph, denoted Qn, whose vertices are the 2 n possible length-n lists of 0s and 1s. For example, the vertices of Q3 are 000, 001, 010, 011, 100, 101, 110, and 111. Two vertices of Qn are adjacent if their lists differ in exactly one position. For example, in Q4, vertices 1101 and 1100 are adjacent (they differ only in their fourth element) but 1100 and 0110 are not adjacent (they differ in positions 1 and 3). Please do the following: a. Show that Q2 is a four-cycle. b. Draw a picture of Q3 and explain why this graph is called a cube. c. How many edges does Qn have? d. Prove that Qn is bipartite. e. Prove that K2;3 is not a subgraph of Qn for any n.