# How to use Mathematica to calculate number of spanning tree?

As the title,The graph g is:

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


My reference book just give the answer is 81. But how to use Mathematica to calculate it? I couldn't find related built-in functions. Anybody can try it?

• I would argue that this is really a math question and not a Mathematica one. See here why: mathworld.wolfram.com/SpanningTree.html – Szabolcs Dec 15 '15 at 15:24
• @Szabolcs It's seem the NumberOfSpanningTrees is what I want.Thanks for your link.Do you think I should close this question? – yode Dec 15 '15 at 15:34
• No, I don't think you have to, I just pointed out that IMO the key is being aware of the math (and not looking for a builtin function). You could write an answer that calculates it without this Combinatorica function, based on one of the two formulae in the MathWorld article. – Szabolcs Dec 15 '15 at 15:55

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}


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

With IGraph/M 0.3.98 or later, you can use

IGSpanningTreeCount[g]


It uses Kirchhoff's theorem, as in the answer by PlaysDice.

It works with directed graphs and non-simple graphs. To make this possible, the standard output of KirchhoffMatrix cannot be used (I would argue that in a sense what KirchhoffMatrix returns is not correct, though one can argue about definitions). For this reason, IGKirchhoffMatrix is also provided.