Take the 2-minute tour ×
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|improve this question
add comment

3 Answers 3

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.