Basic graph counting sequences

Eric W. Weisstein eric at
Wed Aug 20 23:59:42 CEST 2008

On Wed, 20 Aug 2008, David Wilson wrote:

> Number of (connected/unrestricted) n-vertex subgraphs of the undirected 
> complete graph on n vertices, up to isomorphism.
> Starting at n = 0, I'm thinking these begin:
> connected: 1,1,1,2,6,...
> unrestricted: 1,1,2,4,11,...
> Not sure if these are already in the OEIS.
> Also, I counted by hand, so I could be wrong on the counts.

I can't reproduce your counts, so I've either misunderstood or there's a 
problem with them.  If you mean #s of edge-induced subgraphs of K_n having 
n nodes, I believe that's just A002494, whereas the #s of connected ones 
is just A001349...


More information about the SeqFan mailing list