IGraph/M now includes a function to count spanning trees.
In[1]:= Needs["IGraphM`"]
During evaluation of In[1]:= IGraph/M 0.3.99.1 (May 1, 2018)
During evaluation of In[1]:= Evaluate IGDocumentation[] to get started.
In[2]:= IGSpanningTreeCount[HypercubeGraph[3]]
Out[2]= 384
To explore the topic, you might find it useful to generate some more random spanning trees and visualize them.
g = HypercubeGraph[3, VertexLabels -> Automatic]
IGRandomSpanningTree[g, 20] //
DeleteDuplicatesBy[AdjacencyMatrix] //
Map[HighlightGraph[g, #, GraphHighlightStyle -> "Thick"] &]
While this graph has 384 distinct labelled spanning trees, only 6 of them are non-isomorphic.
IGRandomSpanningTree[HypercubeGraph[3], 100] //
DeleteDuplicatesBy[CanonicalGraph]