Editing Eulerian path (section)

=== Complexity issues ===
The number of Eulerian circuits in ''[[Directed graph|digraphs]]'' can be calculated using the so-called '''[[BEST theorem]]''', named after [[N. G. de Bruijn|de '''B'''ruijn]], [[Tatyana Pavlovna Ehrenfest|van Aardenne-'''E'''hrenfest]], [[Cedric Smith (statistician)|'''S'''mith]] and [[W. T. Tutte|'''T'''utte]].  The formula states that the number of Eulerian circuits in a digraph is the product of certain degree factorials and the number of rooted [[Arborescence (graph theory)|arborescences]].  The latter can be computed as a [[determinant]], by the [[matrix tree theorem]], giving a polynomial time algorithm.

BEST theorem is first stated in this form in a "note added in proof" to the Aardenne-Ehrenfest and de Bruijn paper (1951).  The original proof was [[bijective proof|bijective]] and generalized the [[de Bruijn sequence]]s.  It is a variation on an earlier result by Smith and Tutte (1941).

Counting the number of Eulerian circuits on ''undirected'' graphs is much more difficult. This problem is known to be [[Sharp-P-complete|#P-complete]].<ref>Brightwell and [[Peter Winkler|Winkler]], "[http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf Note on Counting Eulerian Circuits]", 2004.</ref> In a positive direction, a [[Markov chain Monte Carlo]] approach, via the ''Kotzig transformations'' (introduced by [[Anton Kotzig]] in 1968) is believed to give a sharp approximation for the number of Eulerian circuits in a graph, though as yet there is no proof of this fact (even for graphs of bounded degree).