# Counting Eulerian trails

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

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.

-
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