Spanning Tree

Author

Eric W. Weisstein
July 11, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/SpanningTree.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/SpanningTree.html.

©2021 Wolfram Research, Inc. except for portions noted otherwise

Minimum leaf number/maximum leaf number

trees=SpanningTrees[GraphData[{5,31}]]

Tally[EdgeCount/@trees]

Tally[LeavesCount/@trees]

Figures

Combinatorica

Context[ShortestPathSpanningTree]

?ShortestPathSpanningTree

ShowGraph[ShortestPathSpanningTree[GridGraph[5,5],13]]

V10

FindSpanningTree[System`GridGraph[{5,5}],ImageSize->Tiny]

FindSpanningTree[{System`GridGraph[{5,5}],13},ImageSize->Tiny]

Kruskal

http://mathematica.stackexchange.com/questions/52056/dual-graph-of-an-arbitrary-planar-graph

(*simple Kruskal's algorithm without sorting*)SpanningTree[graph_]:=Module[{label,edges=EdgeList[graph]},Pick[edges,Table[If[UnsameQ[#1,#2],#2=#1;True,False]&@@Sort[label/@edge],{edge,edges}]]]

System`Graph[SpanningTree[System`GridGraph[{5,5}]],ImageSize->Tiny]

All

SpanningTrees1[g_Graph]:=Module[{n=V[g],e},
e=Select[Subsets[Edges[g]],Union[Flatten[#]]==Range[n]&&TreeQ[FromUnorderedPairs[#]]&];
Graph[List/@#,List/@Vertices[g]]&/@e
]

SpanningTrees2[g_Graph]:=Module[{n=V[g],e},
e=Select[Subsets[Edges[g],{n-1}],TreeQ[FromUnorderedPairs[#]]&];
Graph[List/@#,List/@Vertices[g]]&/@e
]

SpanningTreesPlot[g_,n_:8]:=Partition[GraphPlot[#,Method->None,VertexRenderingFunction->None]&/@SpanningTrees2[g],n,n,{1,1},{}]

GraphicsGrid[{GraphPlot[#,Method->None]&/@{
Graph["C4"],
AddEdges[Graph["C4"],{{1,3}}],AddEdges[Graph["C4"],{{1,3},{2,4}}]}}]

GraphicsGrid[Flatten[{SpanningTreesPlot/@{
Graph["C4"],
AddEdges[Graph["C4"],{{1,3}}],AddEdges[Graph["C4"],{{1,3},{2,4}}]}
},2],Spacings->{Automatic,{150,150,150,0}}
]

Counts

Select[GraphData["Disconnected"],NumberOfSpanningTrees[Graph[#]]≠0&]

Select[GraphData["TuttePolynomial","Defined"],NumberOfSpanningTrees[Graph[#]]≠GraphData[#,"TuttePolynomial"][1,1]&]

Table[Max[NumberOfSpanningTrees/@Graphs[n,"Format"->"V7"]],{n,7}]//Timing

Graphs[#,"Format"->"V7"]&/@Range[8];//Timing//AbsoluteTiming

Table[Max[NumberOfSpanningTrees/@Graphs[n,"Format"->"V7"]],{n,8}]//Timing

Counts by Class

classes={"Andrasfai","AntelopesTour","Antiprism","Apollonian","Barbell","BipartiteKneser","Book","CocktailParty","Complete","CompleteBipartite","CompleteTripartite","CrossedPrism","Crown","CubeConnectedCycle","Cycle","Cyclotomic",(*"Doob",*)"Fan","FiveleapersTour","FoldedCube","Gear","Grid","HalvedCube",(*"Hamming",*)"Hanoi","Helm","Hypercube","Johnson","KingsTour","Kneser","KnightsTour","Ladder","LadderRung","Lattice","MoebiusLadder","Mycielski","Odd","Pan","Path","PermutationStar","Prism","QueensTour","Square","StackedBook","Star","Sun","Sunlet","Tetrahedral","TorusGrid","Triangular","Web","Wheel"};

TableForm[Outer[GraphData[{##},"MolecularTopologicalIndex"]&,classes,Range[10]]/.GraphData[{c_,n_},a_]:>GraphData[{c,{n,n}},a]/.GraphData[{c_,{n_,n_}},a_]:>GraphData[{c,{n,n,n}},a]/.{_Missing->"?",_GraphData->"X"},TableDepth->2,TableHeadings->{classes,None},TableAlignments->{{Left,Right},Automatic}]//Quiet

Parametrized families

Andrasfai

A193126

seq=Table[GraphData[{"Andrasfai",n},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n]//Head

FindGeneratingFunction[seq,x]//Head

FindLinearRecurrence[seq]//Head

Antiprism

A193127

Entity["Graph",{"Antiprism",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Antiprism",n},"SpanningTreeCount"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers&&n>2]

{{GoldenRatio^4,(1/2) (7+3 (Sqrt[5]))},{GoldenRatio^(-4),(1/2) (7-3 (Sqrt[5]))}}//N

Table[(2/5)n(GoldenRatio^(4n)+GoldenRatio^(-4n)-2),{n,20}]//N[#,100]&//Round

Table[(2/5)n(GoldenRatio^(4n)+GoldenRatio^(-4n)-2),{n,20}]//Round

Table[(2/5)n(GoldenRatio^(4n)+GoldenRatio^(-4n)-2),{n,20}]//N[#,100]&//Round

Table[(GoldenRatio^(4n)+GoldenRatio^(-4n)),{n,20}]//FunctionExpand//FullSimplify

Table[LucasL[4n],{n,20}]

Table[2n(LucasL[4n]-2)/5,{n,20}]

FindGeneratingFunction[{0,2,36,384,3528,30250,248832,1989806,15586704,120187008,915304500,6900949462,51599794176,383142771674,2828107288188,20768716848000,151840963183392,1105779284582146,8024954790380544,58059628319357318,418891171182561000},x]//Factor

CoefficientList[Series[((2(1+2 x-16 (x^2)+2 (x^3)+(x^4)))/((((-1+x))^2) (((1-7 x+(x^2)))^2))),{x,0,20}],x]

FullSimplify[SeriesCoefficient[-((2 (-192+1308 x-2261 (x^2)+1424 (x^3)-287 (x^4)+18 (x^5)))/((((-1+x))^2) (((1-7 x+(x^2)))^2))),{x,0,n}],n>2]

r=FindLinearRecurrence[seq]

<<Utilities`EISFormat`

FormatRecurrence[r]

StringReplace[ToString[a[n]==.Table[a[n-k],{k,6}],InputForm],{" "->"","["->"(","]"->")"}]

"a(n) = "<>StringJoin@@Table[If[r[[k]]>0,"+",""]<>Which[r[[k]]==1,"+",r[[k]]==-1,"-",True,ToString[r[[k]]]<>"*"]<>"a("<>"n-"<>ToString[k]<>")",{k,6}]<>"."

LinearRecurrence[{16,-80,130,-80,16,-1},{2,36,384,3528,30250,248832},20]

Apollonian

A193128

seq=Table[GraphData[{"Apollonian",n},"SpanningTreeCount"],{n,6}]

FindSequenceFunction[seq,n]//Head

FindGeneratingFunction[seq,x]//Head

FindLinearRecurrence[seq]//Head

Barbell

seq=Table[GraphData[{"Barbell",n},"SpanningTreeCount"],{n,3,20}]

Table[n^(2 n-4),{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"SpanningTreeCount"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[Drop[seq,2],n-2]//Head

FindGeneratingFunction[seq,x]//Head

Book

A006234

seq=Table[GraphData[{"Book",n},"SpanningTreeCount"],{n,20}]

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

CocktailParty

A193130

seq=Table[GraphData[{"CocktailParty",n},"SpanningTreeCount"],{n,20}]

Table[n^(n-2)(n-1)^n 4^(n-1),{n,20}]

FindSequenceFunction[seq,n]//Head

FindGeneratingFunction[seq,x]//Head

FindLinearRecurrence[seq]//Head

Complete

Entity["Graph",{"Complete",n}]["SpanningTreeCount"]

A000272

seq=Table[GraphData[{"Complete",n},"SpanningTreeCount"],{n,20}]

FindSequenceFunction[seq,n]//Head

Table[n^(n-2),{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["SpanningTreeCount"]

Table[(m^(-1+n)) (n^(-1+m)),{n,10},{m,n}]//Column

CompleteBipartite n×n

A068087

Entity["Graph",{"CompleteBipartite",{n,n}}]["SpanningTreeCount"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"SpanningTreeCount"],{n,20}]

Table[(n^(2n-2)),{n,20}]

FindSequenceFunction[seq,n]//Head

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["SpanningTreeCount"]

Sort[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"SpanningTreeCount"],
(k^(m+n))(m^(n+k))+ (m^(n+k))(n^(k+m))+(n^(k+m))(k^(m+n))
},{n,5},{m,n},{k,m}],2]]

(k^(m+n))(m^(n+k))+ (m^(n+k))(n^(k+m))+(n^(k+m))(k^(m+n))/.{k->n,m->n}

(((2k))^(k+m+n-2))+(((2m))^(k+m+n-2))+(((2n))^(k+m+n-2))/.{k->n,m->n}

CompleteTripartite n×n×n

A193131

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["SpanningTreeCount"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n]//Head

FindGeneratingFunction[seq,x]//Head

FindLinearRecurrence[seq]//Head

CrossedPrism

A193132

seq=Table[GraphData[{"CrossedPrism",2n},"SpanningTreeCount"],{n,2,10}]

FindSequenceFunction[seq,n]//FullSimplify

Table[3 (4^(1+2 n)) (1+n),{n,20}]

FullSimplify[3 (4^(1+2 n)) (1+n)/.n->(n/2)-1]

Table[3 (2^(-3+2 n)) n,{n,4,20,2}]

Table[3 (2^(-3+2 n)) n,{n,2,20,2}]

{12,384,9216,196608,3932160,75497472,1409286144,25769803776,463856467968,8246337208320}/12

FindGeneratingFunction[{0,12,384,9216,196608,3932160,75497472,1409286144,25769803776,463856467968,8246337208320},x]

Series[((12 x)/(((-1+16 x))^2)),{x,0,10}]

Simplify[SeriesCoefficient[((12 x)/(((-1+16 x))^2)),{x,0,n}],n>0]

Table[3 (4^(-1+2 n)) n,{n,20}]

Crown

A193133

seq=Table[GraphData[{"Crown",n},"SpanningTreeCount"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Head

FindGeneratingFunction[seq,x]//Head

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"SpanningTreeCount"],{n,3,8}]

FindSequenceFunction[seq,n-2]

FindGeneratingFunction[seq,x]

Cycle

Entity["Graph",{"Cycle",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Cycle",n},"SpanningTreeCount"],{n,3,20}]

FindSequenceFunction[seq,n-2]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"SpanningTreeCount"],{n,3,14}]

Find

Empty

Entity["Graph",{"Empty",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Empty",n},"SpanningTreeCount"],{n,30}]

Fan

seq=Table[GraphData[{"Fan",{n,n}},"SpanningTreeCount"],{n,2,5}]

FindSequenceFunction[seq,n-1]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

FibonacciCube

FoldedCube

A193134

seq=Table[GraphData[{"FoldedCube",n},"SpanningTreeCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]

FindGeneratingFunction[seq,x]

Gear

A129743

seq=Table[GraphData[{"Gear",n},"SpanningTreeCount"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n>2&&n∈Integers]

Table[(((2-(Sqrt[3])))^n)+(((2+(Sqrt[3])))^n),{n,20}]//Expand

Table[LucasL[2n,Sqrt[2]]-2,{n,3,20}]//Round

LucasL[2Range[20],Sqrt[2]]-2//Round

r=FindLinearRecurrence[seq]

<<Utilities`EISFormat`

FormatRecurrence[r]

LinearRecurrence[{5,-5,1},{2,12,50},20]

Table[-2+(((2-(Sqrt[3])))^n)+(((2+(Sqrt[3])))^n),{n,20}]//Expand

FindGeneratingFunction[%199,x]//Factor

Series[-((2 (1+x))/((-1+x) (1-4 x+(x^2)))),{x,0,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["SpanningTreeCount"]

Table[GraphData[{"Grid",{m,n}},"SpanningTreeCount"],{n,10},{m,n}]//Column

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["SpanningTreeCount"]

A007341

seq=Table[GraphData[{"Grid",{n,n}},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n]//Head

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

Table[((2^((n^2)-1))/(n^2))Product[If[i==j==0,1,2-Cos[((π i)/n)]-Cos[((π j)/n)]],{i,0,n-1},{j,0,n-1}],{n,12}]//Round

Table[((2^((n^2)-1))/(n^2))Product[Piecewise[{{2-Cos[((π i)/n)]-Cos[((π j)/n)],i≠0||j≠0}},1],{i,0,n-1},{j,0,n-1}],{n,12}]//Round

((2^((n^2)-1))/(n^2))Product[Piecewise[{{2-Cos[((π i)/n)]-Cos[((π j)/n)],i≠0||j≠0}},1],{i,0,n-1},{j,0,n-1}]//Timing

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["SpanningTreeCount"]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["SpanningTreeCount"]

A007341

seq=Table[GraphData[{"Grid",{n,n,n}},"SpanningTreeCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]

FindLinearRecurrence[seq]

((2^((n^3)-1))/(n^3))Product[Piecewise[{{3-Cos[((π i)/n)]-Cos[((π j)/n)]-Cos[((π k)/n)],i≠0||j≠0||k≠0}},1],{i,0,n-1},{j,0,n-1},{k,0,n-1}]//Timing

Table[((2^((n^3)-1))/(n^3))Product[Piecewise[{{3-Cos[((π i)/n)]-Cos[((π j)/n)]-Cos[((π k)/n)],i≠0||j≠0||k≠0}},1],{i,0,n-1},{j,0,n-1},{k,0,n-1}],{n,6}]//Round

HalvedCube

A193135

seq=Table[GraphData[{"HalvedCube",n},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n-1]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

Hanoi

A193136

seq=Table[GraphData[{"Hanoi",n},"SpanningTreeCount"],{n,5}]

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Helm

A004146

seq=Table[GraphData[{"Helm",n},"SpanningTreeCount"],{n,3,20}]

Table[LucasL[2n]-2,{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n>2&&n∈Integers]

Table[-2+(GoldenRatio^(-2n))+(GoldenRatio^(2n)),{n,20}]//Round

Table[-2+((((1/2) (3-(Sqrt[5]))))^n)+((((1/2) (3+(Sqrt[5]))))^n),{n,0,20}]//Expand

FindLinearRecurrence[seq]

FindGeneratingFunction[{0,1,5,16,45,121,320,841,2205,5776,15125,39601,103680,271441,710645,1860496,4870845,12752041,33385280,87403801,228826125},x]//Factor

Series[-((x (1+x))/((-1+x) (1-3 x+(x^2)))),{x,0,20}]

Table[LucasL[2n]-2,{n,0,20}]

LinearRecurrence[{5,-8,5,-1},{11,38,112,309},10]

Table[LucasL[2n]-2n-1,{n,0,10}]

Table[-1-2 n+GoldenRatio^(2 n)+GoldenRatio^(-2 n),{n,0,10}]//Round

Table[GraphData[{"Antiprism",n},"ChromaticInvariant"],{n,3,10}]

Hypercube

A006237

Entity["Graph",{"Hypercube",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Hypercube",n},"SpanningTreeCount"],{n,10}]

2^(2^n-1-n)Product[k^Binomial[n,k],{k,n}]

Table[2^(2^n-1-n)Product[k^Binomial[n,k],{k,n}],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Keller",n},"SpanningTreeCount"],{n,5}]

FactorInteger/@seq

King n×n

seq=Table[GraphData[{"King",{n,n}},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n-1]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["SpanningTreeCount"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["SpanningTreeCount"]

seq=Table[GraphData[{"KnightsTour",{n,n}},"SpanningTreeCount"],{n,2,10}]

Ladder

A001353

Entity["Graph",{"Ladder",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Ladder",n},"SpanningTreeCount"],{n,20}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

FindLinearRecurrence[seq]

FindGeneratingFunction[Prepend[seq,0],x]//Factor

FullSimplify[SeriesCoefficient[(x/(1-4 x+(x^2))),{x,0,n}],n>0]

Table[GegenbauerC[n-1,1,2],{n,0,23}]

ChebyshevU[-1+n,2]

GegenbauerC[n-1,1,2]//FunctionExpand

GegenbauerC[n-1,1,2]//FunctionExpand//FullSimplify

Table[-((I Sin[n ArcCos[2]])/(Sqrt[3])),{n,0,23}]//FunctionExpand

Table[((Sinh[n ArcCosh[2]])/(Sqrt[3])),{n,0,23}]//FunctionExpand

GegenbauerC[n-1,1,2]

Table[ChebyshevU[-1+n,2],{n,0,23}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"SpanningTreeCount"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"SpanningTreeCount"],{n,3}]

MoebiusLadder

A020871

Entity["Graph",{"MoebiusLadder",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"MoebiusLadder",n},"SpanningTreeCount"],{n,3,12}]

FindSequenceFunction[seq,n-2]

FindSequenceFunction[{0,3,16,81,392,1815,8112,35301,150544,632043,2620880,10759353,43804824,177105279,711809392,2846259405,11330543648,44929049811,177540878736,699402223137,2747583822760,10766828545767,4209579646289}]

FindGeneratingFunction[seq,x]

FindGeneratingFunction[{0,3,16,81,392,1815,8112,35301,150544,632043,2620880,10759353,43804824,177105279,711809392,2846259405,11330543648,44929049811,177540878736,699402223137,2747583822760,10766828545767,4209579646289},x]

FindLinearRecurrence[seq]

FindLinearRecurrence[{0,3,16,81,392,1815,8112,35301,150544,632043,2620880,10759353,43804824,177105279,711809392,2846259405,11330543648,44929049811,177540878736,699402223137,2747583822760,10766828545767,4209579646289}]

Table[(n/2)(2+(2+Sqrt[3])^n+(2-Sqrt[3])^n),{n,0,20}]//Expand

Series[(3-14*x+26*x^2-14*x^3+3*x^4)/((1-x)*(1-4*x+x^2))^2,{x,0,10}]

FullSimplify[SeriesCoefficient[(3-14*x+26*x^2-14*x^3+3*x^4)/((1-x)*(1-4*x+x^2))^2,{x,0,n}],n>0&&n∈Integers]

Table[2 ChebyshevU[n,2],{n,10}]

Table[1+n+(1/6) ((Sqrt[3]) ((((2-(Sqrt[3])))^n)-(((2+(Sqrt[3])))^n))+3 ((((2-(Sqrt[3])))^(1+n))+(((2+(Sqrt[3])))^(1+n))) n),{n,10}]//Expand

FullSimplify[1+n+(1/6) ((Sqrt[3]) ((((2-(Sqrt[3])))^n)-(((2+(Sqrt[3])))^n))+3 ((((2-(Sqrt[3])))^(1+n))+(((2+(Sqrt[3])))^(1+n))) n)+2 ChebyshevU[n,2]-(n/2)(2+(2+Sqrt[3])^n+(2-Sqrt[3])^n),n∈Integers&&n>3]

FunctionExpand[ChebyshevU[n,2]]

Table[(1/6) (6+(Sqrt[3]) (((2-(Sqrt[3])))^n)-(Sqrt[3]) (((2+(Sqrt[3])))^n)-3 (((2-(Sqrt[3])))^n) (-1+(Sqrt[3])) n+3 (1+(Sqrt[3])) (((2+(Sqrt[3])))^n) n),{n,0,10}]//Expand

Mycielski

A193148

Entity["Graph",{"Mycielski",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Mycielski",n},"SpanningTreeCount"],{n,8}]

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Odd

A193149

Entity["Graph",{"Odd",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Odd",n},"SpanningTreeCount"],{n,6}]

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Path

Entity["Graph",{"Path",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Path",n},"SpanningTreeCount"],{n,20}]

PermutationStar

A193150

seq=Table[GraphData[{"PermutationStar",n},"SpanningTreeCount"],{n,6}]

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Prism

A006235

Entity["Graph",{"Prism",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Prism",n},"SpanningTreeCount"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers&&n>0]

l2=Table[(1/2) (-2+(((2-(Sqrt[3])))^n)+(((2+(Sqrt[3])))^n)) n,{n,0,20}]//Expand

FindLinearRecurrence[seq]

FindGeneratingFunction[l2,x]//Factor

FullSimplify[SeriesCoefficient[((x (1+2 x-10 (x^2)+2 (x^3)+(x^4)))/((((-1+x))^2) (((1-4 x+(x^2)))^2))),{x,0,n}],n>0]

LinearRecurrence[{10,-35,52,-35,10,-1},{0, 1,12,75,384,1805},20]

Queen n×n

A288951

seq=Table[GraphData[{"Queen",{n,n}},"SpanningTreeCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

Rook n×n

A193137

seq=Table[GraphData[{"Rook",{n,n}},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n-1]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"SpanningTreeCount"],{n,10}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"SpanningTreeCount"],{n,4}]

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"SpanningTreeCount"],{n,5}]

Table[(3/20)^(1/4)*(5/3)^(-(n-1)/2)*(540^(1/4))^(3^(n-1)),{n,5}]

FullSimplify[(3/20)^(1/4)*(5/3)^(-(n-1)/2)*(540^(1/4))^(3^(n-1))]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"SpanningTreeCount"],{n,4}]

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n]//Head

FindGeneratingFunction[seq,x]//Head

Star

Entity["Graph",{"Star",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Star",n},"SpanningTreeCount"],{n,25}]

Sun

A193152

seq=Table[GraphData[{"Sun",n},"SpanningTreeCount"],{n,3,20}]

FindSequenceFunction[seq,n-2]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"SpanningTreeCount"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"SpanningTreeCount"],{n,6,10}]

FindSequenceFunction[seq,n-5]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

TorusGrid n×n

A193153

seq=Table[GraphData[{"TorusGrid",{n,n}},"SpanningTreeCount"],{n,3,10}]

FindSequenceFunction[seq,n-2]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

Transposition

Entity["Graph",{"Transposition",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Transposition",n},"SpanningTreeCount"],{n,6}]

Triangular

A193154

seq=Table[GraphData[{"Triangular",n},"SpanningTreeCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

TriangularGrid

A174579

seq=Table[GraphData[{"TriangularGrid",n},"SpanningTreeCount"],{n,10}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"SpanningTreeCount"],{n,10}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"SpanningTreeCount"],{n,10}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"SpanningTreeCount"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"SpanningTreeCount"],{n,10}]

Web

A006235

seq=Table[GraphData[{"Web",n},"SpanningTreeCount"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers&&n≥0]

Wheel

A004146

Entity["Graph",{"Wheel",n}]["SpanningTreeCount"]

seq=Table[GraphData[{"Wheel",n},"SpanningTreeCount"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"SpanningTreeCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Head

Counts algorithms

rands=System`RandomGraph[DegreeGraphDistribution[Table[3,{#}]]]&/@{8,10,12,14,16,18,20,22,24};

Combinatorica

data1=AbsoluteTiming[NumberOfSpanningTrees[CombinatoricaGraph[#]]]&/@rands

Tutte Polynomial

data2=AbsoluteTiming[TuttePolynomial[#,{1,1}]]&/@rands

Direct Matrix tree theorem

SpanningTreeCount[g_System`Graph]:=Det[Drop[Transpose[Drop[Transpose[DiagonalMatrix[VertexDegree[g]]-AdjacencyMatrix[g]],{1}]],{1}]]

SpanningTreeCount[g_System`Graph]:=Det[Rest[Transpose[Rest[Transpose[DiagonalMatrix[VertexDegree[g]]-AdjacencyMatrix[g]]]]]]

Matrix Tree Theorem using DiagonalMatrix and AdjacencyMatrix

The number of nonidentical spanning trees of a graph G is equal to any cofactor of the degree matrix of G minus the adjacency matrix of G (Skiena 1990, p. 235). This result is known as the matrix tree theorem.

Context[Cofactor]

?Cofactor

For "any cofactor" take (i,j)=(1,1)

data3=AbsoluteTiming[Cofactor[Normal[DiagonalMatrix[VertexDegree[#]]-AdjacencyMatrix[#]],{1,1}]]&/@rands

Matrix Tree Theorem using KirchhoffMatrix

data4=AbsoluteTiming[Det[KirchhoffMatrix[#][[1;;-2,1;;-2]]]]&/@rands

data5=AbsoluteTiming[Det[KirchhoffMatrix[#][[2;;,2;;]]]]&/@rands

Compare

data={data1,data2,data3,data4,data5};

Equal@@data[[All,All,2]]

ListPlot[data[[All,All,1]],PlotLegends->Automatic]

Checks

Combinatorica

DeleteCases[{#,GraphData[#,"SpanningTreeCount"],NumberOfSpanningTrees[Graph[#]]}&/@GraphData[;;10],{_,x_,x_}]//Timing

DeleteCases[{#,GraphData[#,"SpanningTreeCount"],NumberOfSpanningTrees[Graph[#]]}&/@GraphData[;;100],{_,x_,x_}]//Timing

DeleteCases[{#,GraphData[#,"SpanningTreeCount"],NumberOfSpanningTrees[Graph[#]]}&/@GraphData[;;500],{_,x_,x_}]//Timing

TuttePolynomial

DeleteCases[{#,GraphData[#,"SpanningTreeCount"],If[ConnectedGraphQ[GraphData[#]], TuttePolynomial[GraphData[#],{1,1}],0]}&/@GraphData[;;10],{_,x_,x_}]//Timing

DeleteCases[{#,GraphData[#,"SpanningTreeCount"],If[ConnectedGraphQ[GraphData[#]], TuttePolynomial[GraphData[#],{1,1}],0]}&/@GraphData[;;12],{_,x_,x_}]//Timing