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 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 statement

Let G = 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.
The BEST theorem states that the number ec of Eulerian circuits in a connected Eulerian graph G is given by the formula
Here t_w is the number of arborescences, which are trees directed towards the root at a fixed vertex w in G. The number t_w 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 = t_w 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. It is also used in the asymptotic enumeration of Eulerian circuits of complete and complete bipartite graphs.

History

The BEST theorem is due to van Aardenne-Ehrenfest and de Bruijn
, §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 which proves the formula for graphs with deg=2 at every vertex.