# BEST theorem

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: de **B**ruijn, van Aardenne-**E**hrenfest, **S**mith and **T**utte.

## Precise statement

Let *G* = (*V*, *E*) be a directed graph. An Eulerian circuit is a directed closed path which 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]\displaystyle{ \operatorname{ec}(G) = t_w(G) \prod_{v\in V} \bigl(\deg(v)-1\bigr)!. }[/math]

Here *t*_{w}(*G*) is the number of arborescences, which are trees directed towards the root at a fixed vertex *w* in *G*. The number *t _{w}(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*

_{v}(

*G*) =

*t*

_{w}(

*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 #P-complete for undirected graphs.^{[1]} It is also used in the asymptotic enumeration of Eulerian circuits of complete and complete bipartite graphs.^{[2]}^{[3]}

## History

The BEST theorem is due to van Aardenne-Ehrenfest and de Bruijn
(1951),^{[4]} §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.

## Notes

- ↑ Brightwell and Winkler, "Note on Counting Eulerian Circuits", CDAM Research Report LSE-CDAM-2004-12, 2004.
- ↑ Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph,
*Combinatorica*, 10 (1995), no. 4, 367–377. - ↑ M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs (in Russian), Proc. 52-nd MFTI Conference (2009), Moscow.
- ↑ van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951). "Circuits and trees in oriented linear graphs".
*Simon Stevin***28**: 203–217.

## References

- Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (in Latin),
*Commentarii Academiae Scientiarum Petropolitanae***8**: 128–140, http://www.math.dartmouth.edu/~euler/pages/E053.html. - Tutte, W. T.; Smith, C. A. B. (1941), "On unicursal paths in a network of degree 4",
*American Mathematical Monthly***48**: 233–237, doi:10.2307/2302716. - van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951), "Circuits and trees in oriented linear graphs",
*Simon Stevin***28**: 203–217, http://repository.tue.nl/597493. - Tutte, W. T. (1984),
*Graph Theory*, Reading, Mass.: Addison-Wesley. - Stanley, Richard P. (1999),
*Enumerative Combinatorics*,**2**,*Cambridge University Press*, ISBN 0-521-56069-1, http://www-math.mit.edu/~rstan/ec/. Theorem 5.6.2 - Aigner, Martin (2007),
*A Course in Enumeration*, Graduate Texts in Mathematics,**238**, Springer, ISBN 3-540-39032-4.

Original source: https://en.wikipedia.org/wiki/BEST theorem.
Read more |