# Graph with multiple Eulerian trails/circuits.

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?

-

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...

-

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.

-
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 '15 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.

-

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.

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).

-