1
$\begingroup$

Looking online I found two different definitions for euler trail. I am wondering if one of them just implicitly assumed what the other definition explicitly stated or whether one is not generally accepted and if so which the general accepted one is:

All edges exactly once, all vertices at least once

Source: https://www.tutorialspoint.com/graph_theory/graph_theory_traversability.htm

Following this definition an unconnected graph never contains an euler trail.

All edges exactly once

Source: https://en.wikipedia.org/wiki/Eulerian_path

Following this definition an unconnected graph can contain an euler trail if a sub-graph is connected and all nodes that aren't part of the sub-graph have no edges.

If you have a solid source (preferably a book), please share it.

$\endgroup$

1 Answer 1

1
$\begingroup$

The definition I often use is the second one: a disconnected graph could contain an euler path.

However, that does not mean that the first definition is wrong.

Unfortunately, Computer Science is a young field (in comparison to maths/physics/other sciences), and its vocabulary is still not well defined. The same name can be described for different (though similar) notions.

In my opinion, the worst examples are often found on trees, where "complete" or "perfect" can designate different kind of trees, where the height can begin at $0$ or $1$ for the empty tree, etc.

What is important is to clearly define used notions so that this kind of ambiguity is cleared.

As for sources, the second definition coincides with the one found in Bondy and Murty (Graph Theory); Jungnickel (Graphs, Networks and Algorithms) and Erickson (Algorithms) agree with this definition; CLRS (Cormen et al., Introduction to Algorithms) defines an Euler tour only for directed strongly connected graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.