# Trees Problem 3

### Solution

#### Base case

The hypercube type $$Q_{0}$$ (zero dimension hypercube) has a single vertex v and no edges. There is one free tree spanning $$Q_{0}$$, i.e. $$Q_{0}$$ itself. Since f(0) is also 1, we've proved the base case.

#### Inductive hypothesis

The n-dimensional hypercube $$Q_n$$ has at least f(n) spanning trees, for $$0 \le n < k$$.

#### Inductive step

Consider $$Q_k$$, where $$1 \ge k$$. $$Q_{k}$$ is constructed using two copies of $$Q_{k-1}$$. Let's call these the left and right subgraphs. The left and right subgraphs are joined together by a set of $$2^{k-1}$$ new edges. Let's call this set of new edges E.

Suppose we take any spanning tree $$T_L$$ in the left subgraph and any spanning tree $$T_R$$ in the right subgraph. Then pick any connecting edge e from E. Joining $$T_L$$ to $$T_R$$ using the edge e will give us a free tree spanning $$Q_k$$.

Let's count how many ways we can construct a spanning tree of this type. By the induction hypothesis there are at least f(k-1) spanning trees in the left subgraph and f(k-1) spanning trees in the right subgraph. Finally, we have $$2^{k-1}$$ choices for the connecting edge. All these choices are independent. So this construction produces at least $$2^{k-1}(f(k-1))^2$$ different spanning trees for $$Q_{k}$$. But $$f(k) = 2^{k-1}(f(k-1))^2$$. So we've produced at least f(k) spanning trees for $$Q_{k}$$. This is what we needed to show.

This procedure doesn't construct all possible spanning trees of $$Q_n$$. There are also spanning trees that cross more than once between the left and right subgraphs.