Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can a graph g that satisfies the necessary condition for having an Eulerian trail have two or more distinct Eulerian trails given a fixed starting vertex?

Or, if a graph has an Eulerian trail, is that the only Eulerian trail in that graph?

share|cite|improve this question

4 Answers 4

up vote 1 down vote accepted

Note that if you find an Eulerian closed trail, you can also traverse it in opposite direction.

Ignoring this, (you consider the backwards trail the same), it is very easy to prove that a simple Eulerian graph has exactly one trail if and only if it is a cycle.

The reason being that if any vertex has degree $\geq 4$, the trail visits the vertex at least twice. Let $W_1$ be the closed walk between the first and second visit and $W_2$ be the closed walk between the third and 4th visit. Then you can simply interchange them and get a different trail...

share|cite|improve this answer

Absolutely there can be more than one, and they can occur in all sorts of ways (including, but not limited to, walking the other way around cycles). Actually, it's quite unusual to have exactly one Eulerian trial.

Here's the 44 distinct Eulerian trials starting at the vertex in the bottom-left corner in the "barn" graph (found by a backtracking algorithm). I've drawn them so the walk starts off light blue and gets darker as we move along.

44 Eulerian trials

share|cite|improve this answer
The graph is very nice. I believe you are right, but I have a hard time following the trails. Arrows would help. Thanks. – Herman Jaramillo Sep 17 at 18:25

Given an Eulerian trail, any subpath that is a loop can be trailed in either direction. Also, if there is a node with index 6 or higher, it is connected to two loops (three in the case of a cycle), which can be traversed in any order. A cycle can start at any vertex.

These are the different general variations I can come up with. If the graph has no loops or is just one loop, then it has basically a unique trail.

share|cite|improve this answer

I like what @Douglas S. Stones did. I do not think that what I am posting here fits in a comment so I am using an "answer" for it.

Douglas found 44 barns. I only found 40. Maybe I am missing 4, but which 4? I am posting two figures. A figure of a tree that I did by hand and brute force, and a drawing of the barns, with arrows and node symbols for clarity.

If anyone find out which 4 barns I am missing, I would be happy.

enter image description here enter image description here

Please observe that if you start at vertex $B$ the solution is the mirror of that found starting at vertex $A$ due to symmetry. If you start at vertices $C$, $D$, or $E$ there is no solution (0 paths, because starting or ending vertices should have odd degree ). No path has Eulerian cycles (since there are two odd degree vertices exactly).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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