We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-edges.


It is known that counting Eulerian orientation in undirected graphs are #P-complete. We have tried to construct some gadget to reduce the general case to 4-regular case, but did not succeed. Any idea about that?


Thank you.



Counting Eulerian Orientation in a 4-regular undirected graph
Let $G$ be a planar graph. Consider a [medial graph](http://en.wikipedia.org/wiki/Knots_and_graphs#Medial_graph) $H=H(G)$, which is always $4$-regular. Often, problems about $G$ can be translated into the language of $H$ and vice versa. Closer to your question, the number of Eulerian orientations of $H$ is "almost" an evaluation of the Tutte polynomial:
$$(\ast) \qquad \sum\_{O} 2^{\alpha(O)} = 2\cdot T\_G(3,3),$$
where the summation is over all Eulerian orientations $O$ of $H$, and $\alpha(O)$ is the number of *saddle vertices* (i.e. where the orientation is in-out-in-out in cyclic order). This is due to Las Vergnas (JCTB 45, 1988). My former student Mike Korn and I generalized this [here](http://www.math.ucla.edu/~pak/papers/tutte7color.pdf). 


Of course, evaluations of the Tutte polynomial of planar graphs, including at ($3,3)$, are pretty much all #P-hard (with a few known exceptions), see D.J.A. Welsh, *Complexity: knots, colourings and counting* book (1993). Now, there is a bijective proof of $(\ast)$, which maps orientations $O$ into certain subsets of edges of $G$. It is possible that when you map the number of orientations without weight you still get a hard-to-compute stat. sum, which will prove what you want. 


