Trees Problem 3


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.


The base case should be h=0, because that's the dimension of the smallest hypercube. Did your base case check the claim for this hypercube, i.e. check that there are at least f(0) spanning trees?

In the inductive hypothesis, did you clearly state the range of heights for which the claim is supposed to hold? Is the top value in this range (k-1 in the above) one less than the dimension of the hypertree you analyzed in the inductive step (k in the above)?

Did you force the dimension k to be larger than the base case dimension (i.e. zero)? This allows us to divide the hypercube of dimension k into two smaller hypercubes.

Finally, does your proof have lots of words? Correct spelling and punctuation? Sensible division into paragraphs? If you posted this on github, would the students next term be able to understand how the construction works? No? Then write it out properly.