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

Richard J. Mathar mathar at mpia-hd.mpg.de
Mon Sep 14 13:34:07 CEST 2015


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.
a(3) counts the triangle.
a(4) counts the quadrangle,
     the quadrangle with a diagonal edge,
     and the quadrangle with two (crossing) diagonal edges (tetrahedral graph).
a(5) counts the pentagon,
    the pentagon with a diagonal
    the pentagon with two non-crossing diagonals
    the pentagon with two crossing diagonals
    the pentagon with three crossing diagonals
    the pentagon with two crossing and one non-crossing diagonal
    the two triangles with a common node
    the pentatope (5 diagonals)
a(6) counts the hexagon (6-cycle),
    the hexagon with the short diagonal,
    the hexagon with the long diagonal,
    the hexagon with two short non-crossing parallel diagonals,
    the hexagon with two non-crossing (long and short) diagonals
         that share a common node on the pentagon's perimeter,
    the hexagon with two short non-crossing diagonals,
    the hexagon with two long crossing diagonals,
    the hexagon with two crossing (long and short) diagonals,
    the hexagon with two crossing (both short) diagonals,
    the quadrangle and the triangle with a common point,
    the quadrangle with diagonal with a triangle that has a common point not touched by the diagonal.
    the quadrangle with diagonal with a triangle that has a common point touched by the diagonal.
    the quadrangle with two diagonals with a triangle that has a common point
    ..plus further cases of the pentagon with three diagonals
One might count this more systematically by removing 
edge sets from the complete graph on n nodes.
Roughly related to A07112, A007111, A136281.

RJM



More information about the SeqFan mailing list