[seqfan] Re: Seqfan Digest, Vol 17, Issue 2

Brendan McKay bdm at cs.anu.edu.au
Sun Feb 7 22:48:00 CET 2010

I seem to recall a specific proposal that "Euler graph" and
"Eulerian graph" mean different things, but I don't know where
it was.  In any case it is about 40 years too late since both
names have been used for both meanings many times each.

It is fun to see that although the Mallows and Sloane paper (1975)
uses "Euler graph", the review of their paper in Math Reviews by the
famous enumerator Bob Robinson used "Eulerian graph".  This despite
Robinson having previously used "Euler graph" in his own work.

I also noticed the following in a seminal 1962 paper of Ron Read
"Euler graphs on labelled nodes":
    Throughout most of the paper we shall be dealing with graphs
    whose nodes have even valencies but which may or may not be
    connected. For convenience we shall refer to these graphs as Euler
    graphs, although the usage is not, strictly speaking, correct.

Btw, there is also some specific infinite graph called "the Euler graph".


> Message: 4
> Date: Thu, 04 Feb 2010 20:08:52 -0500
> From: franktaw at netscape.net
> Subject: [seqfan] Re: Number of Euler graphs: A002854 or something
> 	else?
> To: seqfan at list.seqfan.eu
> "Eulerian graph" and "Euler graph" may be two different things.  
> "Eulerian numbers" and "Euler numbers" certainly are (not that either 
> of those has anything to do with the graphs).
> Franklin T. Adams-Watters
> -----Original Message-----
> From: Brendan McKay <bdm at cs.anu.edu.au>
> 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.

More information about the SeqFan mailing list