Euler circuits for the graph

eulerian-pathgraph theory

How many different Euler circuits are there in the graph that begins at $A$ and then visits $D$ as the immediate next vertex?

My answer is $16$, and I suppose I have counted all possible such Euler circuits. I wonder whether I have missed additionally possible paths, and would be welcomed to know that. enter image description here

Best Answer

You are correct.

Notice that such an Euler circuit must use $e_2$. So you can reduce the problem to finding the number of Euler trails starting at $C$ and ending at $A$ in $G - D$.

The graph G minus D

Think of an Euler trail in this case as a sequence of five edges $e_{i_1}e_{i_2}\cdots e_{i_5}$. Perhaps one of the easier ways to count is to single out an edge, say $e_3$, and count the number of valid sequences with $e_3$ in the first position, then the second, and so on. Since we are starting at $C$, you may notice that a sequence representing an Euler trail can only have $e_3$ in the first, third, and fifth position. You obtain

  1. First: $4$ trails. Traverse $e_3$. There are $4$ ways to go from $A$ to $C$, back to $A$, that is two choices from $A$ to $B$, two choices from $B$ to $C$, and the way back is determined.

  2. Third: $8$ trails. You can go $CBCABA$ of which there are four ways, or $CBACBA$, another four ways.

  3. Fifth: $4$ trails, similar to the first case.

While this answer is long winded, at least in thinking this way you can be confident that you've exhausted all possibilities in your count. I believe in general it is hard ($NP$-hard?) to count the number of Euler circuits in a given undirected graph.