0
$\begingroup$

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?

  • 1
    In these slides, it is noted that the general problem of counting Euler tours in undirected graphs is #P-complete. http://www.cs.rochester.edu/~stefanko/Talks/EULER.pdf2012-06-04

3 Answers 3

1

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.

  • 0
    (Sorry, its been long & I forgot all that I learnt at that time, I don't remember anything now, so cant reply now)2016-12-19
2

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

  • 0
    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.2012-06-04
1

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.

  • 0
    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.2012-06-04