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