graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a part of discrete mathematics, the BEST theorem gives a product formula for the number of

Eulerian circuit In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...

s in

directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...

(oriented)

graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

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

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 may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

and the

indegree In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

is equal to

outdegree In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

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 :

\operatorname(G) = t_w(G) \prod_ \bigl(\deg(v)-1\bigr)!.

Here ''t''_''w''(''G'') is the number of arborescences, which are

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

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

determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...

, by the version of the

matrix tree theorem In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time ...

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. It is also used in the asymptotic enumeration of Eulerian circuits of

complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...

and

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..Electronic edition page 17. Graph theory i ...

s.M.I. Isaev
Asymptotic number of Eulerian circuits in complete bipartite graphs
(in

Russian Russian(s) refers to anything related to Russia, including: *Russians (, ''russkiye''), an ethnic group of the East Slavic peoples, primarily living in Russia and neighboring countries *Rossiyane (), Russian language term for all citizens and peo ...

), Proc. 52-nd MFTI Conference (2009), Moscow.

History

The BEST theorem is due to van Aardenne-Ehrenfest and de Bruijn (1951), §6, Theorem 6. Their proof is

bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

and generalizes the

de Bruijn sequence In combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet ''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a substring (i.e., as a ''contiguous'' subseq ...

s. 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

References

*. *. *. *. *. Theorem 5.6.2 *. {{Authority control Directed graphs Theorems in graph theory