BEST Theorem
The BEST theorem, short for the de Bruijn-van Aardenne-Ehrenfest-Smith-Tutte theorem, gives a product formula for the number of directed Eulerian cycles in an Eulerian digraph.
Let G be a finite strongly connected directed graph such that the indegree and outdegree of every graph vertex are equal. If d_v is the outdegree of vertex v and t_r(G) is the number of spanning arborescences whose arcs are directed toward a fixed vertex r, then the number of Eulerian cycles of G that begin with a prescribed arc leaving r is
If the first arc leaving r is not prescribed, this count is multiplied by d_r. Counts of Eulerian cycles modulo cyclic shifts require the corresponding normalization for the chosen convention.
The theorem applies to directed Eulerian graphs; counting Eulerian cycles in undirected graphs requires additional handling of orientations.
The number t_r(G) of rooted arborescences can be computed by a directed form of the matrix tree theorem. Since Hamiltonian cycles in a line digraph correspond to Eulerian cycles in the original directed graph, the BEST theorem can also be used to count Hamiltonian cycles in iterated line-digraph constructions.
See also
Arborescence, Eulerian Cycle, Eulerian Digraph, Line Digraph, Matrix Tree TheoremExplore with Wolfram|Alpha
References
Jackson, D. M. and Goulden, I. P. "Sequence Enumeration and the de Bruijn-Van Aardenne Ehrenfest-Smith-Tutte Theorem." Canad. J. Math. 31, 488-495, 1979. https://doi.org/10.4153/CJM-1979-054-x.Tutte, W. T. and Smith, C. A. B. "On Unicursal Paths in a Network of Degree 4." Amer. Math. Monthly 48, 233-237, 1941. https://doi.org/10.1080/00029890.1941.11991103.van Aardenne-Ehrenfest, T. and de Bruijn, N. G. "Circuits and Trees in Oriented Linear Graphs." Simon Stevin 28, 203-217, 1951.Cite this as:
Weisstein, Eric W. "BEST Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BESTTheorem.html