BEST theorem
Template:Short description In graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. The name is an acronym of the names of people who discovered it: N. G. de Bruijn, Tatyana van Aardenne-Ehrenfest, Cedric Smith and W. T. Tutte.
Precise statementEdit
Let G = (V, E) be a directed graph. An Eulerian circuit is a directed closed trail that visits each edge exactly once. In 1736, Euler showed that G has an Eulerian circuit if and only if G is connected and the indegree is equal to 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 tw(G) is the number of arborescences, which are trees directed towards the root at a fixed vertex w in G. The number tw(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 tv(G) = tw(G) for every two vertices v and w in a connected Eulerian graph G.
ApplicationsEdit
The BEST theorem shows that the number of Eulerian circuits in directed graphs can be computed in polynomial time, a problem which is #P-complete for undirected graphs.<ref>Brightwell and Winkler, "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 and complete bipartite graphs.<ref>Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.</ref><ref>M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs Template:Webarchive (in Russian), Proc. 52-nd MFTI Conference (2009), Moscow.</ref>
HistoryEdit
The BEST theorem is due to van Aardenne-Ehrenfest and de Bruijn (1951),<ref name="AB">Template:Cite journal</ref> §6, Theorem 6. Their proof is bijective and generalizes the de Bruijn sequences. 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.