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.

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!

share|improve this question
    
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. –  Thomas Andrews Nov 14 '11 at 22:28
    
Ok, thank you very much ;) –  Alexandar Živkovič Nov 14 '11 at 22:45
add comment

1 Answer

up vote 1 down vote accepted

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 the two problems to be roughly equally difficult.

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.