In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a part of discrete mathematics

Discrete mathematics

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...

, the BEST theorem gives a product formula for the number of Eulerian circuits in directed

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

 (oriented) graphs

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

. The name is an acronym of the names of people who discovered it: de Bruijn, van Aardenne-Ehrenfest

Tatyana Pavlovna Ehrenfest

Tatyana Pavlovna Ehrenfest, later van Aardenne-Ehrenfest, was a Dutch mathematician. She was the daughter of Paul Ehrenfest and Tatyana Alexeyevna Afanasyeva .Tatyana Ehrenfest was born in Vienna, and spent her childhood in St Petersburg...

, Smith and Tutte

W. T. Tutte

William Thomas Tutte, OC, FRS, known as Bill Tutte, was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher, a major German code system, which had a significant impact on the Allied...

.

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

Connected component

Connected components are part of topology and graph theory, two related branches of mathematics.* For the graph-theoretic concept, see connected component .* In topology: connected component .Implementations:...

 and the indegree is equal to outdegree at every vertex. In this case G is called Eulerian. We denote these in- and out-degree 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 this formula:


Here t_w(G) is the number of arborescences

Arborescence (graph theory)

In graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v....

, which are trees

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

 directed towards the root at a fixed vertex w in G. The number t_w(G) can be computed as a determinant

Determinant

In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

, 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

Sharp-P

In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...

-complete for undirected graphs. It is also used in the asymptotic enumeration of Eulerian circuits of complete

Complete graph

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

 and complete bipartite graph

Complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...

s.

History

The BEST theorem was first stated in this form in a "note added in proof" to the Aardenne-Ehrenfest and de Bruijn paper (1951). The original proof was bijective

Bijective proof

In combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of...

 and generalized the de Bruijn sequence

De Bruijn sequence

In combinatorial mathematics, a k-ary De Bruijn sequence B of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly...

s. It is a variation on an earlier result by Smith and Tutte (1941).