Is it possible for a graph to have an Euler circuit and an Euler path?

Question

Is it true that an Euler path should have two vertices of odd degree and an Euler circuit should have no vertices of odd degree? Is it therefore impossible to have a graph with both an Euler path and an Euler circuit?

Answer 1

This link (which you have linked in the comment to the question) states that having Euler path and circuit are mutually exclusive. The definition of Euler path in the link is, however, wrong - the definition of Euler path is that it's a trail, not a path, which visits every edge exactly once. And in the definition of trail, we allow the vertices to repeat, so, in fact, every Euler circuit is also an Euler path.

Answer 2

No. Why? Let us start with the definitions first.

Euler Circuit: A closed trail in the graph which has all the edges in the graph.

Euler Path: An open trail in the graph which has all the edges in the graph.

Crudely, suppose we have an Euler path in the graph. Now assume we also have an Euler circuit. But the Euler path has all the edges in the graph. Now if the Euler circuit has to exist then it too must have all the edges. So such a situation is not possible.

Also, suppose we have an Euler Circuit, assume we also have an Euler path, but from analysis as above, it is not possible.

One can also verify from the conditions of Euler Path and Euler Circuit existence:

Euler Circuit: Iff all vertices have even degree (and the graph has at most 1 nontrivial component)

Euler Path: Iff exactly two vertices have odd degrees and all others have even degree (and the graph has 1 nontrivial component)

What you are thinking is however true for Hamiltonian Graphs....[Hamiltonian Cycle $\implies$ Hamiltonian Path]

Answer 3

If a graph has an Euler circuit, i.e. a trail which uses every edge exactly once and starts and ends on the same vertex, then it is impossible to also have a trail which uses every edge exactly once and starts and ends on different vertices. (This is because the start and end vertices must have odd degree in the latter case, but even degree in the former case.)

Whether this means Euler circuit and Euler path are mutually exclusive or not depends on your definition of "Euler path". Some people say that an Euler path must start and end on different vertices. With that definition, a graph with an Euler circuit can't have an Euler path. Other people say that an Euler path has no restriction on start and end vertices. With that definition, a graph with an Euler circuit automatically has an Euler path (which is the same as its Euler circuit).