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

[Brendan McKay]

I did a quick survey of graph theory books on my shelves (about
a dozen) and found that ALL of them defined an "Eulerian graph"
to be a graph with an Eulerian tour ( = Eulerian circuit).

So while I am quite familiar with the definition that only requires
all degrees to be even (and used it myself at least once), it is
certainly not accepted as a standard. Also, the definition "having
an Eulerian tour" is the one that makes the most historical sense.

Interestingly, I found about 5 books with the following "theorem":
  A graph is Eulerian (i.e., has an Eulerian tour) iff it is connected
  and every vertex has even degree.
This is FALSE, since a graph remains Eulerian (by the definition in 
those books) if isolated vertices are added.

Max's edits to Wikipedia need to be replaced by a discussion of the
variations of definition in the literature.  And OEIS should state
the definition being used for A002854.

Cheers, Brendan.


> Message: 4
> Date: Thu, 28 Jan 2010 11:59:58 -0500
> From: "N. J. A. Sloane" <njas at research.att.com>
> Subject: [seqfan] Re: Number of Euler graphs: A002854 or something
> 	else?
> To: seqfan at list.seqfan.eu
> Cc: njas at research.att.com
> Message-ID: <201001281659.o0SGxwrn005682 at prim.research.att.com>
> Content-Type: text/plain; charset=us-ascii
> 
> Max,  I think you have misunderstood the definition of Euler graph.
> An Euler graph is a graph with every node having even degree.
> 
> I will add a comment to A002854 to clarify this.
> 
> References for this definition are 
> 
> 1. the "classic" paper which underlies A002854, namely
> 
> %D A002854 C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880.
> 
> (did you look at it?)
> 
> and 2. the earlier references that it cites.
> 
> Your definition :
> 
> > 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.
> 
> is not right.
> 
> As you say, one should be very careful before changing the classic sequences!
> 
> Neil
> 
> ------------------------------
> 
> Message: 5
> Date: Thu, 28 Jan 2010 13:04:27 -0500
> From: Max Alekseyev <maxale at gmail.com>
> Subject: [seqfan] Re: Number of Euler graphs: A002854 or something
> 	else?
> To: njas at research.att.com
> Cc: seqfan at list.seqfan.eu
> Message-ID:
> 	<d3dac271001281004l1a6cd180o7badd1b1547f650a at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
> 
> On Thu, Jan 28, 2010 at 11:59 AM, N. J. A. Sloane <njas at research.att.com> wrote:
> > Max, ?I think you have misunderstood the definition of Euler graph.
> 
> I've just followed the definitions given in MathWorld and Wikipedia.
> In particular, MathWorld defines Eulerian Graph as "a graph containing
> an Eulerian cycle."
> http://mathworld.wolfram.com/EulerianGraph.html
> 
> That's especially confusing since MathWorld and A002854
> cross-reference each other.
> 
> > An Euler graph is a graph with every node having even degree.
> >
> > I will add a comment to A002854 to clarify this.
> 
> That settles things up. Thanks!
> 
> > Your definition :
> >
> >> 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.
> >
> > is not right.
> 
> Well, at least I did not invent this definition.
> 
> Regards,
> Max
> 
> ------------------------------
> 
> Message: 6
> Date: Thu, 28 Jan 2010 13:32:29 -0500
> From: Max Alekseyev <maxale at gmail.com>
> Subject: [seqfan] Re: Number of Euler graphs: A002854 or something
> 	else?
> To: njas at research.att.com
> Cc: seqfan at list.seqfan.eu
> Message-ID:
> 	<d3dac271001281032q79fb9ba8s9a4b0f19cf8d6831 at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
> 
> On Thu, Jan 28, 2010 at 11:59 AM, N. J. A. Sloane <njas at research.att.com> wrote:
> 
> > References for this definition are
> >
> > 1. the "classic" paper which underlies A002854, namely
> >
> > %D A002854 C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880.
> 
> I've corrected the definition given in Wikipedia article and cited
> this reference there.
> http://en.wikipedia.org/wiki/Eulerian_path
> Further improvements are welcome. In particular, there is still a
> confusing definition of semi-Eulerian graphs.
> 
> Regards,
> Max