How to use Mathematica to calculate number of spanning tree?

From the Properties and Relations section of TuttePolynomial (thanks to Szabolcs):

TuttePolynomial[g,{1,1}] counts the number of spanning trees in the graph:

In[1]:= TuttePolynomial[GridGraph[{2, 3}], {1, 1}]

Out[1]= 15

g = Graph[{1 <-> 4, 1 <-> 5, 1 <-> 6, 2 <-> 4, 2 <-> 5, 2 <-> 6, 
   3 <-> 4, 3 <-> 5, 3 <-> 6}, GraphLayout -> "BipartiteEmbedding"]

TuttePolynomial[g, {1, 1}]

$\ $ 81

For a large(r) connected graph, an approach using Kirchhoff's theorem is much faster and uses less memory than TuttePolynomial. We generate the Laplacian matrix for the graph (Mathematica calls this KirchhoffMatrix), drop one row and one column from the KirchhoffMatrix and calculate the Determinant of the adjusted matrix.

rand = RandomGraph[DegreeGraphDistribution[Table[3, {30}]]]

AbsoluteTiming[TuttePolynomial[rand, {1, 1}]]

AbsoluteTiming[kirk = KirchhoffMatrix[rand]; 
               spans = Det[kirk[[1 ;; -2, 1 ;; -2]]]]

(* Out *)
{30.262097, 12181794623}
{0.005720, 12181794623}