2
$\begingroup$

I want to make sure I understand the definition of an Eulerian Graph / Trail / Cycle / Circut.

I'm reading Schaum's Discrete Mathematics Outline which gives the following definitions:

A graph G is called an Eulerian Graph if there exists a closed traversable trail, called an Eulerian trail.

It then goes on to say that:

A finite connected graph is Eulerian if and only if each vertex has even degree.

I then read the following in Wikipedia:

Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree

...not every Eulerian graph possesses an Eulerian cycle

So which one is right? Can a graph be Eulerian, having only vertices of even degree, yet not contain an Eulerian circuit?

Also, isn't there a distinction between an Eulerian trail and an Eulerian Cycle / Circuit?

$\endgroup$
7
  • $\begingroup$ There is a distinction between an Eulerian trail/path and an Eulerian circuit, but note that the Schaum’s Outline definition specified a closed Eulerian trail $-$ which would be a circuit. $\endgroup$
    – Brian M. Scott
    Jan 26, 2012 at 9:08
  • $\begingroup$ For the question about Eulerian graphs, note that Wikipedia also says: ‘The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree.’ When they say that not every Eulerian graph possesses an Eulerian cycle, they’re using the second definition and thinking of graphs that are not connected. $\endgroup$
    – Brian M. Scott
    Jan 26, 2012 at 9:10
  • $\begingroup$ So the only case of a graph whose vertices are all even but doesn't contain an Eulerian circuit would be disconnected graphs, correct? $\endgroup$
    – Robert S. Barnes
    Jan 26, 2012 at 9:19
  • $\begingroup$ That’s correct. They would be unions of Eulerian graphs in the stronger sense. $\endgroup$
    – Brian M. Scott
    Jan 26, 2012 at 9:21
  • $\begingroup$ I edited the Wikipedia definition to be clearer about the two possible senses of the term. It's now a bit redundant, but that's better than being confusing. $\endgroup$
    – Ilmari Karonen
    Jan 26, 2012 at 13:20

1 Answer 1

Reset to default
4
$\begingroup$

The problem here is that there are two definitions of Eulerian graph. To quote the Wikipedia article that you cite:

The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree.

The Schaum’s Outline text seems to be using the first of these meanings; the statement in the Wikipedia article that ‘not every Eulerian graph possesses an Eulerian cycle’ is using the second. A graph with every vertex of even degree need not be connected; if it is connected, it’s Eulerian by either definition, but if it’s not connected, it’s Eulerian by the second definition and not by the first.

As you say, there is a distinction between an Eulerian trail/path and an Eulerian circuit/cycle. However, a closed path is a circuit, so the definition in the Schaum’s Outline text is equivalent to the usual one.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .