BEST theorem
In graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. 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 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 tw(G) is the number of arborescences, which are trees directed towards the root at a fixed vertex w in G. The number tw(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 tv(G) = tw(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.[1] It is also used in the asymptotic enumeration of Eulerian circuits of complete and complete bipartite graphs.[2][3]
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 and generalized the de Bruijn sequences. It is a variation on an earlier result by Smith and Tutte (1941).
Notes
- ^ Brightwell and Winkler, "Note on Counting Eulerian Circuits", CDAM Research Report LSE-CDAM-2004-12, 2004.
- ^ Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.
- ^ M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs (in Russian), Proc. 52-nd MFTI Conference (2009), Moscow.
References
- Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140.
- W. T. Tutte and C. A. B. Smith, On Unicursal Paths in a Network of Degree 4. Amer. Math. Monthly, 48 (1941), 233-237.
- T. van Aardenne-Ehrenfest and N. G. de Bruijn, Circuits and trees in oriented linear graphs, Simon Stevin, 28 (1951), 203-217.
- W.T. Tutte, Graph Theory, Addison-Wesley, Reading, Mass., 1984.
- Stanley, Richard P. (1999). Enumerative Combinatorics, Vol. 2. Cambridge University Press. ISBN 0-521-56069-1.
- Aigner, Martin, A Course in Enumeration, 2007, ISBN 3-540-39032-4.