[seqfan] Number of Euler graphs: A002854 or something else?

[Max Alekseyev]

SeqFans,

I believe there is something wrong with sequence A002854 related to
Euler graphs.

Let us assume the conventional definition of Euler graphs:
a graph is Euler if there exists an Euler cycle, i.e., a cycle that
goes through every edge in the graph exactly once.

It is well known that a connected graph is an Euler graph if and only
if each vertex has an even degree. In this respect let us consider the
following three types of unlabeled graphs:

T1) generic (not necessarily connected) Euler graphs;
T2) connected Euler graphs;
T3) generic (not necessarily connected) graphs with every vertex
having an even degree.

Note that in this list there are no "connected graphs with every
vertex of even degree" since such graphs are exactly the connected
Euler graphs, i.e., graphs of type T2.

Let N1(n), N2(n), N3(n) denote the number of graphs respectively of
types T1, T2, T3 on n nodes.

OEIS claims that A002854(n) = N1(n) while A003049(n) = N2(n).

However, I think that in reality we have A002854(n) = N3(n).

First, it is easy to see that any graph of type T1 consists of a
"large" connected component of type T2 and a number of isolated
vertices.
Therefore, we have N1(n) = N2(1) + N2(2) + N2(3) + ... + N2(n) (where
we simply sum up over the size of large connected component).
>From the values listed in A003049, we can easily get the sequence N1(n):
1, 1, 2, 3, 7, 15, 52, 236, 2018, 33044, 1181670, ...
which is different from A002854 and is missing in the OEIS.
The first discrepancy between A002854(n) and N1(n) occurs at n=6,
where A002854(n) - N1(n) = 1. This one stands for the graph on 6
vertices consisting of two disjoint cycles on three vertices each.
This graph has type T3 but not T1.

Second, it is easy to see that any graph of type T3 consists of
connected components, each of which is a graph of type T2. Therefore,
by Riddell's formula the sequence N3(n) represents an Euler transform
of N2(n); and vice versa, N2(n) is an inverse Euler transform of
N3(n). At the same time, A003049 claims:

%F A003049 Inverse Euler transform of A002854. (This is equivalent to
the Robinson formula.) - Frank Adams-Watters
(FrankTAW(AT)Netscape.net), Jul 24 2006

In other words, it means that A002854(n) = N3(n).

I'm not sure what is the best way to fix the error in the OEIS. I
would simply make a correction to the description of A002854 but it
heavily refers to the literature on Euler graphs and I'm not sure how
to introduce the correction smoothly. Moreover, it's an old sequence
and has to be treated carefully. That's why I'm raising this
discussion in SeqFan.

I also admit a possibility that generic Euler graphs are actually
defined as graphs of type T3. But I never saw such a definition and it
contradicts to definitions given in MathWorld and Wikipedia.

In any case, it make sense to add the missing sequence N1(n) but only
after the current confusion is cleared.

Regards,
Max

P.S. It is interesting that MathWorld
http://mathworld.wolfram.com/EulerianGraph.html refers to the sequence
A002854 and gives illustration of all graphs up to 5 nodes. If there
were an illustration of all  A002854(6)=16 graphs on 6 nodes, we would
observe a graph consisting of two disjoint cycles on 3 vertices each,
that is not an Euler graph according to the definition given there.