[Graphs with n edges]

[Brendan McKay]

* Christian G. Bower <bowerc at usa.net> [021010 10:07]:
> > 
> > There are two lists in the data base, starting with 
> > "1,1,1,3,5,12,30,79,227", the A046091 and A002905.
> > Both state that they list the number of graphs with n edges.
> 
> No!
> 
> A002905 states it's the number of [connected] graphs with n edges
> A046091 states it's the number of [connected] PLANAR graphs with n edges
> i.e. those graphs that can be drawn in the plane without edges crossing.
> 
> They are two different sequences.
> 
> By the way, the offset on A002905 should be 0, not 1.

I agree with all of the above.  Neil:  note the error
listed in the previous sentence.

However...

> Now that I think about it, there are 2 connected graphs with zero edges:
> the empty graph and the one node graph. Thus a(0) should be 2.

Sometimes graph theorists find that allowing the null graph
(not "empty" graph, that just means a graph with no edges)
to exist makes some proof get slicker, but generally speaking
the smallest graph is considered to be that with 1 vertex.

This practice follows the path of least resistance: allowing
the null graph causes much more trouble than it is worth.
It has no automorphism group, it cannot be imbedded on the
sphere obeying Euler's formula, it is connected and acyclic
but has too many edges to be a tree, etc etc..  It is an
exception to so many things that the community (or most of it)
decided that the only good null graph is a dead null graph.

Harary and Read once discussed this issue in a paper called
"Is the null-graph a pointless concept?".

Brendan.