Counting Eulerian Orientation in a 4-regular undirected graph 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.
 A: Let $G$ be a planar graph. Consider a 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. 
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. 
