How to find the number of spanning trees for a cube? 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. 
 A: 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

A: 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.
A: 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$
