I'm trying to figure out how many different Eulerian circuits there are in the following graph.
I have found one Eulerian circuit so far (see photo below, start- and end point to the far left). How would I go about to find more and is there a method of mathematical nature that I could use to identify more circuits.
Best Answer
We will count the number of Euler circuits unique up to shifting the starting point of the cycle: thus only the direction and relative order of edges matters and not which edge is the "first".
Notice that vertices of degree $2$ don't contribute meaningfully to this count, since any circuit entering such a vertex is constrained to immediately exit along the remaining edge. We may replace each of the four vertices of degree $2$ by a (distinguished) edge, resulting in a double $4$-cycle with each twin edge being made of distinguishable colours (say $A$ and $B$). This graph will have exactly the same number of unique Euler circuits as the original.
Consider an Euler circuit in this new graph, which is constrained at any given time to either go clockwise or counterclockwise around the square. We consider separately two cases:
1) No changes in direction: Fix an arbitrary starting vertex. The path goes around the square exactly twice, either clockwise or counterclockwise. There are 4 additional choices it could make on the first loop: for each edge, it can go along the $A$ edge or the $B$ edge (on the second pass, it has to use the remaining one). This gives $2 \cdot 2^4$ Euler circuits, but we have overcounted by a factor of $2$, because the circuit passes through the starting vertex twice. So this case yields $16$ distinct circuits.
2) At least one change in direction: Suppose the path changes direction at vertex $v$. It is easy to see that it must then go all the way around the square once, change direction a second time at $v$ and then go back. (Any earlier change in direction will disconnect the graph and prevent completion of the Euler circuit.). In your example this occurs at the "southwest" vertex. So there is exactly two direction-changes at one vertex. There are four choices for this vertex. Once we choose this, the circuit is composed of a clockwise path and a counterclockwise path (up to uniqueness it makes no difference which one we consider to be "first"). The clockwise segment can choose the $A$ or $B$ edge at each segment, while the counterclockwise segment takes the other half. This results in $4 \cdot 2^4 = 64$ choices for this case.
So the total number of Euler circuits is $80$. But I welcome any corrections in case I missed a symmetry and overcounted.