(a) For n ≥ 2, let V denote the vertices in Qn. For 1 ≤ k ≤ ℓ ≤ n, define the relation R on V as follows: If w, x ∈ V, then w R x if w and x have the same bit (0, or 1) in position k and the same bit (0, or 1) in position k of their binary labels. [For example, if n = 7 and k = 3 ℓ = 6, then 1100010 R0000011.] Show that R is an equivalence relation. How many blocks are there for this equivalence relation? How many vertices are there in each block? Describe the subgraph of Qn induced by the vertices in each block.
(b) Generalize the results of part (a).