Compute the minimum spanning tree in hypercube $Q_{k}$

Question

Suppose that in the hypercube $Q_{k}$, each edge whose endpoints differ in coordinate i has weight $2^{i}$. Compute the minimum weight of a spanning tree.
I know I can use Kruskal's algorithm but not sure how to keep track of not having cycles when I proceed the algorithm.

Answer 1

Here is a general outline/hint.

It is easy to see that the first $2^{k-1}$ stages of Kruskal's will include all of the edges with weight $1$, leaving $2^{k-1}$ pairs of vertices joined by an edge. Considering the new graph $Q'_k$ who vertices are these $2^{k-1}$ pairs, where the weight of the edge joining two pairs is the minimum weight edge joining some vertex in one pair to some vertex in the other, it is easy to show that $Q_k'$ is isomorphic to $Q_{k-1}$, except all edge weights are doubled. Furthermore, completing these pairs to a spanning tree for $Q_k$ is exactly like finding a spanning tree for $Q_{k}'\cong Q_{k-1}$. Therefore, you can proceed by induction. The final spanning tree will have $2^{k-1}$ edges of weight $1$, $2^{k-2}$ edges of weight $2$, $2^{k-3}$ edges of weight $4$, etc.