An equally natural question is to ask for the number of distinct Euler
tours in a graph. For the case of directed graphs, the BEST theorem due
to De Bruijn, Ehrenfest, Smith and Tutte gives an exact formula that gives
the number of Euler tours in a directed graph [1]}, [2]}
which yields a polynomial time algorithm via a determinant computation.
For undirected graphs, no such closed form expression is known and the
computational problem is #P-complete [3]}. In fact, the problem
is #P-complete even when restricted to 4-regular planar graphs [4]}.
So exactly computing the number of Euler tours is not in
polynomial time unless \(\mbox{{\sf \#P}}= \mbox{{\sf P}}\) .
