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

-

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.

-