BEST theorem

<h2 id="precise-statement">Precise statement</h2>
Let G = (V, E) be a directed graph. An Eulerian circuit is a directed closed trail that visits each edge exactly once. In 1736, <a href="/facts/Leonhard_Euler/z2fsbjgj">Euler</a> showed that G has an Eulerian circuit if and only if G is <a href="/facts/Connected_graph/FSNjsYhz">connected</a> and the <a href="/facts/Directed_graph/YBdfQ0um">indegree</a> is equal to <a href="/facts/Directed_graph/YBdfQ0um">outdegree</a> 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

ec
        ⁡
        (
        G
        )
        =
        
          t
          
            w
          
        
        (
        G
        )
        
          ∏
          
            v
            ∈
            V
          
        
        
          
            (
          
        
        deg
        ⁡
        (
        v
        )
        −
        1
        
          
            )
          
        
        !
        .
      
    
    {\displaystyle \operatorname {ec} (G)=t_{w}(G)\prod _{v\in V}{\bigl (}\deg(v)-1{\bigr )}!.}

Here tw(G) is the number of <a href="/facts/Arborescence_(graph_theory)/qFKvoaLJ">arborescences</a>, which are <a href="/facts/Tree_(graph_theory)/TCWk4Joy">trees</a> directed towards the root at a fixed vertex w in G. The number tw(G) can be computed as a <a href="/facts/Determinant/eGYqJ2TF">determinant</a>, by the version of the <a href="/facts/Matrix_tree_theorem/pptIpEVc">matrix tree theorem</a> for directed graphs. It is a property of Eulerian graphs that tv(G) = tw(G) for every two vertices v and w in a connected Eulerian graph G.

<h2 id="applications">Applications</h2>
The BEST theorem shows that the number of Eulerian circuits in directed graphs can be computed in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>, a problem which is <a href="/facts/Sharp-P-complete/M6QgPJY6">#P-complete</a> for undirected graphs.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> It is also used in the asymptotic enumeration of Eulerian circuits of <a href="/facts/Complete_graph/AYD6hUqI">complete</a> and <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graphs</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="history">History</h2>
The BEST theorem is due to van Aardenne-Ehrenfest and de Bruijn
(1951),<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> §6, Theorem 6.
Their proof is <a href="/facts/Bijective_proof/wQsz192E">bijective</a> and generalizes the <a href="/facts/De_Bruijn_sequence/jExlpx9H">de Bruijn sequences</a>. 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.

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Leonhard_Euler/z2fsbjgj">Euler, L.</a> (1736), <a href="http://www.math.dartmouth.edu/~euler/pages/E053.html">"Solutio problematis ad geometriam situs pertinentis"</a>, Commentarii Academiae Scientiarum Petropolitanae (in Latin), 8: 128–140.</li>
<li><a href="/facts/W._T._Tutte/8VbfbzU6">Tutte, W. T.</a>; <a href="/facts/Cedric_Smith_(statistician)/1R1ExNv0">Smith, C. A. B.</a> (1941), "On unicursal paths in a network of degree 4", <a href="/facts/American_Mathematical_Monthly/Te6CHvkg">American Mathematical Monthly</a>, 48 (4): 233–237, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2302716">10.2307/2302716</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2302716">2302716</a>.</li>
<li><a href="/facts/Tatyana_Pavlovna_Ehrenfest/H6fIp0MK">van Aardenne-Ehrenfest, T.</a>; <a href="/facts/Nicolaas_Govert_de_Bruijn/pr2Hbxfm">de Bruijn, N. G.</a> (1951), <a href="http://repository.tue.nl/597493">"Circuits and trees in oriented linear graphs"</a>, <a href="/facts/Simon_Stevin_(journal)/1nl2jYTB">Simon Stevin</a>, 28: 203–217.</li>
<li><a href="/facts/W._T._Tutte/8VbfbzU6">Tutte, W. T.</a> (1984), Graph Theory, Reading, Mass.: Addison-Wesley.</li>
<li><a href="/facts/Richard_P._Stanley/8bQ4QrLM">Stanley, Richard P.</a> (1999), <a href="http://www-math.mit.edu/~rstan/ec/">Enumerative Combinatorics</a>, vol. 2, <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-56069-1. Theorem 5.6.2</li>
<li><a href="/facts/Martin_Aigner/yq5j37yW">Aigner, Martin</a> (2007), A Course in Enumeration, Graduate Texts in Mathematics, vol. 238, Springer, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-39032-9.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Brightwell and Winkler, "Note on Counting Eulerian Circuits", CDAM Research Report LSE-CDAM-2004-12, 2004. <a href="/wiki/Peter_Winkler" target="_blank">/wiki/Peter_Winkler</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377. <a href="/wiki/Brendan_McKay_(mathematician)" target="_blank">/wiki/Brendan_McKay_(mathematician)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs Archived 2010-04-15 at the Wayback Machine (in Russian), Proc. 52-nd MFTI Conference (2009), Moscow. <a href="http://www.mipt.ru/nauka/52conf/materialy/07-FUPM1-site.pdf#page=56" target="_blank">http://www.mipt.ru/nauka/52conf/materialy/07-FUPM1-site.pdf#page=56</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951). "Circuits and trees in oriented linear graphs". Simon Stevin. 28: 203–217. <a href="/wiki/Tatyana_Pavlovna_Ehrenfest" target="_blank">/wiki/Tatyana_Pavlovna_Ehrenfest</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

BEST theorem open-in-new

BEST theorem