BEST Theorem - Precise Statement

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

$\operatorname{ec}(G) = t_w(G) \prod_{v\in V} \bigl(\deg(v)-1\bigr)!$

Here t_w(G) is the number of arborescences, which are trees directed towards the root at a fixed vertex w in G. The number t_w(G) 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(G) = t_w(G) for every two vertices v and w in a connected Eulerian graph G.

Read more about this topic: BEST Theorem

Famous quotes containing the words precise and/or statement:

“... he held it one of the prettiest attitudes of the feminine mind to adore a man’s pre- eminence without too precise a knowledge of what it consisted in.”
—George Eliot [Mary Ann (or Marian)

“A sentence is made up of words, a statement is made in words.... Statements are made, words or sentences are used.”
—J.L. (John Langshaw)