I'm trying to calculate (or, show) the number of spanning trees in the hypercube $Q_n$. I know I must come to
$$\tau(Q_n) = \prod^{n}_{i=2} (2i)^{\begin{pmatrix} n \\ i\end{pmatrix}}$$
I thought it would be easiest to work via induction and then the Cartesian product bit (to make the "gluing 2 $Q_{n-1}$ together" more "rigorous"); ie,
$$ Q_n \cong K_2 \times_1 \ldots \times_{n-1} K_2 $$
to denote that $Q_n$ is isomorphic to the Cartesian product of $n$ $K_2$'s. Now, I'll use $L$ to denote the graph Laplacian:
$$L(K_2^{n-1} \times K_2) = L(K_2^{n-1}) \otimes I_2 + I_{2^{n-1}} \otimes L(K_2)$$
but it's at this point that I'm struggling... for Kirchoff's/ Matrix Tree Theorem, I'm interested in the determinant, but I run into the determinant of that sum; recall $|A+ B| = |A| + |B| + |A|\cdot \text{Tr}|A^{-1}B|$. We can calculate
$$ |L(K_2^{n-1}) \otimes I_2| = |L(K_2^{n-1})|^2 \cdot 1^{2^{n-1}}$$ $$ |I_{2^{n-1}} \otimes L(K_2)| = 1^2 \cdot 0 = 0 $$
but I do not see a clean way to get the trace below beyond the brute force computation, though even then I am not sure what I can say about the inverse.
$$ \text{Tr}\left[(L(K_2^{n-1}) \otimes I_2)^{-1} \cdot (I_{2^{n-1}} \otimes L(K_2)) \right]$$
and I can already feel that taking that and working back towards the desired is not so nice (presuming it doesn't just work out to zero somehow).
Any hints or nudges in the right direction?
Working through the details related to Misha's comment, I was really stuck on a wild goose chase...
First, for graphs $G$ and $H$, we know that if $L(G)$ has $m$ eigenvalues $\lambda_i$ and $L(G)$ has $n$ eigenvalues $\mu_j$, then $L(G \times H)$ has $mn$ eigenvalues $\lambda_i + \mu_j$. (This can be seen via Kronecker product properties)
The claim is, as Misha notes, the eigenvalues are of the form $2i$ for $i = 0, \ldots, n$ with multiplicity $n \choose i$. We can compute the eigenvalues for $L(K_2)$ eigenvalues:
$$ L(K_2) = \begin{pmatrix} 1& -1 \\ -1 & 1 \end{pmatrix}$$
So, eigenvalues of $0, 2$ with multiplicity $1,1$ each.
By induction, base case is $K_2 \times K_2$, which can also be done directly: we have $0,2,4$ with multiplicity $1,2,1$ respectively.
Then for the inductive step, the eigenvalues are $$\{0 + 2i : i=0, \ldots, n-1\} \cup \{2 + 2i: i = 0, \ldots, n-1\} = \{2i : i = 0 \ldots, n\}$$
so that is done. For multiplicity, notice that $2\cdot 0$ and $2\cdot n$ are of multiplicity $1 = {n \choose 0} = {n \choose n}$ each. Then, for any $i = 1, \ldots, n-1$, corresponding to adding $2$ and adding $0$, we have
$${n-1 \choose i -1} + {n-1 \choose i} = {n \choose i}$$
With Kirchoff's
$$ \tau(Q_n) = \frac{1}{2^n} \prod_{i=1}^n (2i)^{n \choose i} = \prod_{i=2}^n (2i)^{n \choose i}$$