# [seqfan] Re: Counting simple graphs with node degree >=2

Georgi Guninski guninski at guninski.com
Wed Sep 16 14:01:44 CEST 2015

On Mon, Sep 14, 2015 at 01:34:07PM +0200, Richard J. Mathar wrote:
> Is the number of simple (loopless, undirected, no multi-edges, connected,
> unlabelled) graphs on n nodes in the OEIS, counting only graphs where
> each node has at least degree 2 (or simpler: where each edge is part
> of at least one circuit)?
>
> My manual count proposes this starts a(3)=1, a(4)=3, a(5)>=8, a(6)>=13.

In sage with nauty package, from 3 to 9 I get:
1 , 3 , 11 , 61 , 507 , 7442 , 197772

So far this appears
A004108 Number of n-node unlabeled connected graphs without endpoints.

sage code, you can run it in a browser in the cloud:

def mathar1():
"""
sage code
requires optional package nauty
"""
for n in [ 3 .. 9]:
cou=0
for g in graphs.nauty_geng("%s -c -d2"%n):
#-c means connected, -d \delta=2
cou += 1
print cou,",",
sys.stdout.flush()