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:

“Writing prejudicial, off-putting reviews is a precise exercise in applied black magic. The reviewer can draw free- floating disagreeable associations to a book by implying that the book is completely unimportant without saying exactly why, and carefully avoiding any clear images that could capture the reader’s full attention.”
—William Burroughs (b. 1914)

“The parent is the strongest statement that the child hears regarding what it means to be alive and real. More than what we say or do, the way we are expresses what we think it means to be alive. So the articulate parent is less a telling than a listening individual.”
—Polly Berrien Berends (20th century)