How to find the number of spanning trees for a cube?

Question

Can you tell me a way of finding the total number of spanning trees in a $Q_d$ undirected labelled graph for $d = 3$.

I know that the answer is 384, but the way (I know there are many.) of finding it escapes me.

Answer 1

Extending the answer of Pegah. The eigenvalues of the Laplacian of $Q_d$ are $(0,2,\ldots,2d)$ with respective multiplicities ${d \choose k}.$

Now the product of the nonzero eigenvalues divided by $2^d$ is the number of spanning trees of $G.$ For $d = 3$ we have

$\tau(Q_3) = 2^3 \cdot 4^3 \cdot 6^1/2^3 = 384,$ as confirmed by Juan.

for the lazy ones one can also use Sage math

sage: G = graphs.CubeGraph(3)
sage: G.spanning_trees_count()
384

Answer 2

One possible solution is using the Tutte polynomial.

The Tutte polynomial for the octahedron graph is

$T \left( x,y \right) =12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{ y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2}+25\,{x}^{2}+29\,{y}^{4}+15\,{y }^{5}+5\,{y}^{6}+6\,{y}^{4}x+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^ {3}+7\,{x}^{4}+{x}^{5} $

Now, the number of spanning trees can be computed as $T(1,1)$, then we obtain

$T \left( 1,1 \right) =384$

Answer 3

One of the most interesting theorems about the number of spanning trees of a graph is matrix tree theorem.

Matrix Tree Theorem states that: Given a loopless graph G with vertex set $v_1,v_2,...,v_s$, let D be a diagonal matrix in which $d_{ii}=deg_G(v_i)$, and let A be the adjacency matrix of G. Define $Q:=D-A$. If $Q^*$ is a matrix obtained by deleting row $s$ and column $t$ of $ Q$, then the number of spanning trees of G is equal to $(-1)^{t+s}det(Q^*)$.

You can find the proof here:

Introduction to Graph Theory / Douglas B. West / page 86

For your question, $Q^*$ will be a $7 \times 7$ matrix, but it still isn't hard to calculate it's determinant.