Function Repository Resource:

# SpanningTreeCount

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]:=
 Out[1]=
 In[2]:=
 Out[2]=

### Properties and Relations (4)

A tree contains exactly one spanning tree:

 In[3]:=
 Out[3]=
 In[4]:=
 Out[4]=

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

 In[5]:=
 Out[5]=
 In[6]:=
 Out[6]=

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

 In[7]:=
 Out[7]=
 In[8]:=
 Out[8]=
 In[9]:=
 Out[9]=

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

 In[10]:=
 Out[10]=
 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=
 In[13]:=
 Out[13]=

## Version History

• 1.0.0 – 01 June 2020