Question: Consider the n-cube, where n ≥ 1. (You my think of this as a graph or as a geometric object) The vertices of the n-cube are labeled with length-n binary strings, and there is one vertex for every such string. Two vertices u = (u1,...,un) and v = (v1,...,vn) are adjacent if and only if u and v differ in exactly one position.
(a) What is the degree sequence for the n-cube? Explain.
(b) Let en be the number of edges in the n-cube. What are e1,e2,e3,e4?
(c) Find a recurrence relation for en and explain the presence of each term.
(d) Find and prove a closed form for en. (You may wish to use over counting rather than using the recurrence relation.)
(e) For which n is the graph of the n-cube planar? Justify.