Reference no: EM131587229

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 = (u₁,...,u_n) and v = (v₁,...,v_n) 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 e₁,e₂,e₃,e₄?

(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.