1
$\begingroup$

I have an assignment to count all nonequivalent Eulerian trails in the famous kindergarten graph:

enter image description here

I think that there are $12$ distinct trails in total, but I have reached this conclusion by drawing them all. On top of that, I think that I can reason like this:
The graph has 2 odd vertices, so the trail has to start from one of them and end in the other one. If I start from vertex $A$, I can go in $3$ different routes and each one then splits one more time to $2$ other. So that is $3 \times 2 = 6$ different trails. And another $6$ if I start from $B$, using the same reasoning.

My question is - is my reasoning correct? And is there any general algorithm for counting Eulerian trails in undirected graphs? I know it exists for directed graphs.

Thanks in advance!

  • 0
    Yes. Essentially, it amounts to realizing that there are three paths between $A$ and $B$, and you can go from $A$ to $B$ in three different ways, then from $B$ back to $A$ in two different ways, then you are left with only one way back to $B$. This case is relatively easy because all the other nodes have degree $2$, so once entered. So, given a permutation of the path segments $(A,E,B)$, $(A,B)$, and $(A,C,D,B)$, and an initial point chosen from $A$ or $B$, you get a different path, and that covers all paths.2011-11-14
  • 0
    Ok, thank you very much ;)2011-11-14

1 Answers 1

2

According to Wikipedia,

Counting the number of Eulerian circuits on undirected graphs is much more difficult [than on directed graphs]. This problem is known to be #P-complete. In a positive direction, a Markov chain Monte Carlo approach, via the Kotzig transformations (introduced by Anton Kotzig in 1968) is believed to give a sharp approximation for the number of Eulerian circuits in a graph.

A couple of references are given.

I know that circuits are not trails, but I expect that the two problems to be roughly equally difficult.