Editing BEST theorem

{{Short description|Formula used in graph theory}}
In [[graph theory]], a part of [[discrete mathematics]], the '''BEST theorem''' gives a product formula for the number of [[Eulerian circuit]]s in [[directed graph|directed]] (oriented) [[Graph (discrete mathematics)|graphs]].  The name is an acronym of the names of people who discovered it: [[N. G. de Bruijn]], [[Tatyana van Aardenne-Ehrenfest]], [[Cedric Smith (statistician)|Cedric Smith]] and [[W. T. Tutte]].

== Precise statement == 
Let ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') be a directed graph.  An Eulerian circuit is a directed closed trail that visits each edge exactly once.  In 1736, [[Leonhard Euler|Euler]] showed that ''G'' has an Eulerian circuit if and only if ''G'' is [[connected graph|connected]] and the [[Directed graph#Indegree and outdegree|indegree]] is equal to [[Directed graph#Indegree and outdegree|outdegree]] at every vertex.  In this case ''G'' is called Eulerian.  We denote the indegree of a vertex ''v'' by deg(''v'').

The BEST theorem states that the number ec(''G'') of Eulerian circuits in a connected Eulerian graph ''G'' is given by the formula

:<math>
\operatorname{ec}(G) = t_w(G) \prod_{v\in V} \bigl(\deg(v)-1\bigr)!.
</math>

Here ''t''<sub>''w''</sub>(''G'') is the number of [[Arborescence (graph theory)|arborescences]], which are [[tree (graph theory)|trees]] directed towards the root at a fixed vertex ''w'' in ''G''. The number ''t<sub>w</sub>(G)'' can be computed as a [[determinant]], by the version of the [[matrix tree theorem]] for directed graphs.  It is a property of Eulerian graphs that ''t''<sub>''v''</sub>(''G'')&nbsp;=&nbsp;''t''<sub>''w''</sub>(''G'') for every two vertices ''v'' and ''w'' in a connected Eulerian graph ''G''.

== Applications ==
The BEST theorem shows that the number of Eulerian circuits in directed graphs can be computed in [[polynomial time]], a problem which is [[Sharp-P-complete|#P-complete]] for undirected graphs.<ref>Brightwell and [[Peter Winkler|Winkler]], "[http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf Note on Counting Eulerian Circuits]", CDAM Research Report LSE-CDAM-2004-12, 2004.</ref>  It is also used in the asymptotic enumeration of Eulerian circuits of [[complete graph|complete]] and [[complete bipartite graph]]s.<ref>[[Brendan McKay (mathematician)|Brendan McKay]] and Robert W. Robinson, [http://cs.anu.edu.au/~bdm/papers/euler.pdf Asymptotic enumeration of eulerian circuits in the complete graph], ''[[Combinatorica]]'', 10 (1995), no. 4, 367–377.</ref><ref>M.I. Isaev, [http://www.mipt.ru/nauka/52conf/materialy/07-FUPM1-site.pdf#page=56 Asymptotic number of Eulerian circuits in complete bipartite graphs] {{Webarchive|url=https://web.archive.org/web/20100415082547/http://www.mipt.ru/nauka/52conf/materialy/07-FUPM1-site.pdf#page=56 |date=2010-04-15 }} (in [[Russian language|Russian]]), Proc. 52-nd MFTI Conference (2009), Moscow.</ref>

== History ==
The BEST theorem is due to van Aardenne-Ehrenfest and de Bruijn
(1951),<ref name="AB">{{cite journal|author1-link=Tatyana Pavlovna Ehrenfest|first1=T.|last1=van Aardenne-Ehrenfest|author2-link=Nicolaas Govert de Bruijn|first2=N. G.|last2=de Bruijn|title=Circuits and trees in oriented linear graphs|journal=[[Simon Stevin (journal)|Simon Stevin]]|volume=28|year=1951|pages=203–217}}</ref> §6, Theorem 6.
Their proof is [[bijective proof|bijective]] and generalizes the [[de Bruijn sequence]]s.  In a "note added in proof", they refer to an earlier result by Smith and Tutte (1941) which proves the formula for graphs with deg(v)=2 at every vertex.

== Notes ==
{{Reflist}}

== References ==
*{{citation|last=Euler|first=L.|authorlink=Leonhard Euler|url=http://www.math.dartmouth.edu/~euler/pages/E053.html|title=Solutio problematis ad geometriam situs pertinentis|language=Latin|journal=Commentarii Academiae Scientiarum Petropolitanae|volume=8|year=1736|pages=128–140}}.
*{{citation|first1=W. T.|last1=Tutte|author1-link=W. T. Tutte|first2=C. A. B.|last2=Smith|author2-link=Cedric Smith (statistician)|title=On unicursal paths in a network of degree 4|journal=[[American Mathematical Monthly]]|volume=48|year=1941|issue=4 |pages=233–237|jstor=2302716|doi=10.2307/2302716}}.
*{{citation|author1-link=Tatyana Pavlovna Ehrenfest|first1=T.|last1=van Aardenne-Ehrenfest|author2-link=Nicolaas Govert de Bruijn|first2=N. G.|last2=de Bruijn|title=Circuits and trees in oriented linear graphs|journal=[[Simon Stevin (journal)|Simon Stevin]]|volume=28|year=1951|pages=203–217|url=http://repository.tue.nl/597493}}.
*{{citation|first=W. T.|last=Tutte|authorlink=W. T. Tutte|title=Graph Theory|publisher=Addison-Wesley|location=Reading, Mass.|year=1984}}.
*{{citation|authorlink=Richard P. Stanley|last=Stanley|first=Richard P.|year=1999|url=http://www-math.mit.edu/~rstan/ec/|title=Enumerative Combinatorics|volume=2|publisher=[[Cambridge University Press]]|isbn=0-521-56069-1}}. Theorem 5.6.2
*{{citation|authorlink=Martin Aigner|last=Aigner|first=Martin|title=A Course in Enumeration|year=2007|isbn=978-3-540-39032-9|series=Graduate Texts in Mathematics|volume=238|publisher=Springer}}.

{{Authority control}}

[[Category:Directed graphs]]
[[Category:Theorems in graph theory]]