# How many Euler tours exist in a given graph?

A Euler tour is defined like that:

Let $G = (V, E)$ be a graph and $C$ a circuit in $G$.

$C$ is called Euler tour $\Leftrightarrow$ every edge $e \in E$ is exactly once in the circuit.

If a graph $G$ has at least one Euler tour $C$ that starts with $v \in V$, can $G$ have another Euler tour that also starts with $v$ and does not simply go into the other direction?

-
In these slides, it is noted that the general problem of counting Euler tours in undirected graphs is #P-complete. cs.rochester.edu/~stefanko/Talks/EULER.pdf – utdiscant Jun 4 '12 at 13:45

Certainly. The usual proof that Euler circuits exist in every graph where every vertex has even degree shows that you can't make a wrong choice. So if you have two vertices of degree $4$, there will be more than one circuit. Specifically, think of $K_5$, the complete graph on $5$ vertices. Any permutation of $12345$ is a start of a Euler circuit-then hit the other edges either way around, $48$ of them starting at any given vertex. There are more, too, as $1521345241$ is another which returns to start not halfway through.

-
There might not be completely wrong choices, but you might choose a wrong path, which you must then alter afterwards. For example consider two cycles joined in a vertex, where the tour start in a vertex which is not the common vertex of the cycles. Here you could choose to walk around the first cycle, but you want to use the other cycle also. – utdiscant Jun 4 '12 at 11:57
Ok, I've tried the $K_5$ example. When I name the vertexes clockwise from 1 to 5, I get those two Euler tours: 1-2-3-4-5-1-3-5-2-4-1 and the other one is 1-3-5-2-4-1-2-3-4-5-1. By the way, no permutation of 12345 is an Euler circuit, as you have to visit all edges exactly once. – Martin Thoma Jun 4 '12 at 12:44

Can't you always go around in the other direction?

-
Okay, this was not what I thought of :-P But you're right, so I gave you an upvote and I will clarify my question. – Martin Thoma Jun 4 '12 at 12:38

Consider a graph in the shape of a figure 8. If you start in the middle of the 8, you can go around the top lobe, then around the bottom lobe, or you can go around the bottom lobe, then the top lobe.

Moreover, you have a choice of two directions for each lobe. This makes 4 circuits in all. Even if you throw out circuits that are the reversed versions of other circuits, this only cuts the number of circuits in half, leaving 2.

You can add a third lobe to get a graph with 4 circuits; a graph with $n$ lobes has $2^{n-1}$ circuits, or $2^n$ if you allow reversals.

-