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:

“In their precise tracings-out and subtle causations, the strongest and fieriest emotions of life defy all analytical insight.”
—Herman Melville (1819–1891)

“He that writes to himself writes to an eternal public. That statement only is fit to be made public, which you have come at in attempting to satisfy your own curiosity.”
—Ralph Waldo Emerson (1803–1882)