Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 GraphCount

Source Notebook

Find the number of fundamentally different graphs of a specified size

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

ResourceFunction["GraphCount"][n]

gives the number of nonisomorphic undirected graphs with n vertices.

ResourceFunction["GraphCount"][{n,m}]

gives the number of nonisomorphic undirected graphs with n vertices and m edges.

ResourceFunction["GraphCount"][n,type]

give the number of nonisomorphic graphs with n vertices and of the specified type.

ResourceFunction["GraphCount"][{n,m},type]

give the number of nonisomorphic graphs with n vertices, m edges and of the specified type.

Details and Options

In ResourceFunction["GraphCount"][…,type], type can be either "Directed" or "Undirected".
ResourceFunction["GraphCount"][n] is equivalent to ResourceFunction["GraphCount"][n,"Undirected"].

Examples

Basic Examples (3) 

Find the number of fundamentally different (nonisomorphic) graphs with four vertices:

In[1]:=
ResourceFunction["GraphCount"][4]
Out[1]=

Show the graphs:

In[2]:=
graph4 = GraphData /@ GraphData[4];
In[3]:=
Multicolumn[graph4]
Out[3]=
In[4]:=
Length[graph4]
Out[4]=

Confirm that they are nonisomorphic:

In[5]:=
IsomorphicGraphQ @@@ Flatten[Select[ Table[{graph4[[i]], graph4[[j]]}, {i, 1, Length[graph4]}, {j, 1, i - 1}], # =!= {} &], 1]
Out[5]=

Find the number of graphs with four vertices and three edges:

In[6]:=
ResourceFunction["GraphCount"][{4, 3}]
Out[6]=

Show the graphs:

In[7]:=
Select[graph4, (EdgeCount[#] == 3) &]
Out[7]=
In[8]:=
Length[%]
Out[8]=

The number of nonisomorphic directed graphs with three vertices:

In[9]:=
ResourceFunction["GraphCount"][3, "Directed"]
Out[9]=

Properties and Relations (2) 

The number of simple directed unlabeled graphs on n nodes for n=1,2,… is given by OEIS A000273:

In[10]:=
ResourceFunction["GraphCount"][#, "Directed"] & /@ Range[0, 14]
Out[10]=

The number of simple directed unlabeled graphs on n nodes with m edges is given by OEIS A052283:

In[11]:=
triangle[k_] := Table[ResourceFunction["GraphCount"][{n, #}, "Directed"] & /@ Range[0, n (n - 1)], {n, 0, k}]
In[12]:=
Flatten[triangle[6]]
Out[12]=

Or as a triangle:

In[13]:=
triangle[4]
Out[13]=
In[14]:=
% // Column
Out[14]=

Sum the rows:

In[15]:=
Total /@ %%
Out[15]=

This is the same as:

In[16]:=
ResourceFunction["GraphCount"][#, "Directed"] & /@ Range[0, 4]
Out[16]=

Neat Examples (1) 

The number of graphs grows rapidly with the number of vertices:

In[17]:=
Table[{i, ResourceFunction["GraphCount"][i]}, {i, 20}] // Grid
Out[17]=

Version History

  • 2.0.0 – 30 September 2020
  • 1.0.0 – 19 June 2020

Related Resources

License Information