Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 SpanningTreeCount

Source Notebook

Count the number of labeled spanning trees in a graph

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["SpanningTreeCount"][g]

gives the number of labeled spanning trees of the graph g.

Details and Options

A spanning tree of a graph g is a tree whose vertex set includes all the vertices of g and whose edges are all contained in the edge set of g.
In a labeled tree, each vertex is given a unique label.

Examples

Basic Examples (1) 

Find the number of spanning trees of a graph:

In[1]:=
RandomGraph[{5, 6}]
Out[1]=
In[2]:=
ResourceFunction["SpanningTreeCount"][%]
Out[2]=

Properties and Relations (4) 

A tree contains exactly one spanning tree:

In[3]:=
StarGraph[10]
Out[3]=
In[4]:=
ResourceFunction["SpanningTreeCount"][%]
Out[4]=

A cycle on n vertices contains exactly n spanning trees, since deleting any edge creates a tree:

In[5]:=
CycleGraph[10]
Out[5]=
In[6]:=
ResourceFunction["SpanningTreeCount"][%]
Out[6]=

The number of spanning trees of a complete graph is nn-2, as was proved by Cayley:

In[7]:=
CompleteGraph[#] & /@ {1, 2, 10}
Out[7]=
In[8]:=
ResourceFunction["SpanningTreeCount"] /@ %
Out[8]=
In[9]:=
#^(# - 2) & /@ {1, 2, 10}
Out[9]=

GraphData[name,"SpanningTreeCount"] gives the number of spanning trees for a named graph:

In[10]:=
GraphData["BannerGraph", {"Graph", "SpanningTreeCount"}]
Out[10]=
In[11]:=
ResourceFunction["SpanningTreeCount"][First[%]]
Out[11]=
In[12]:=
GraphData[{"Cycle", 5}, {"Graph", "SpanningTreeCount"}]
Out[12]=
In[13]:=
ResourceFunction["SpanningTreeCount"][First[%]]
Out[13]=

Version History

  • 1.0.0 – 01 June 2020

License Information