BEST theorem

The BEST theorem counts Eulerian circuits in a finite directed Eulerian graph using the number of spanning in-arborescences and the vertices’ outdegrees.

Connect

Eulerian circuit: A closed trail in a graph that uses every edge exactly once. The theorem counts these circuits in directed graphs.
Euler's theorem (graph theory): A criterion characterizing connected graphs that have an Eulerian circuit through vertex degrees. Its directed analogue motivates the balance condition used by BEST.
Irving J. Good: A British statistician and mathematician known for work in probability, statistics, and combinatorics. Good published an early proof and popularized the theorem’s name.
De Bruijn sequence: A cyclic sequence in which every possible length-n string over a fixed alphabet occurs exactly once. Euler circuits in de Bruijn graphs count and construct these sequences.
Directed graph: A graph whose edges have assigned directions, from a tail vertex to a head vertex. The theorem applies to directed graphs with balanced indegrees and outdegrees.
Indegree: The number of directed edges entering a vertex. In an Eulerian directed graph, each vertex’s indegree equals its outdegree.
Frederick T. E. Stearn: A mathematician whose work included an early formulation of the Euler-circuit counting result now called BEST. Stearn’s initials contribute to the theorem’s name.
De Bruijn graph: A directed graph whose vertices and edges encode overlapping strings of a fixed length. Its Euler circuits correspond to cyclic sequences with exhaustive substring coverage.
Spanning in-arborescence: A directed spanning tree in which every vertex has a unique directed path to a designated root. The tree count in the formula is rooted at the circuit’s starting vertex.
Spanning tree: A connected, cycle-free subgraph containing every vertex of a graph. An in-arborescence is the directed, rooted form counted in the theorem.