In R.P. Stanley's book, Enumerative Combinatorics, Vol.2, paragraph 5.6, there is an intuitive proof of the BEST therem, which states that the number of eulerian tours in a balanced digraph $D$ with vertices in $V$ is given by


$\epsilon(D) = t(D) \prod\_{v' \in V} (\mathrm{out}\_{v'}(D)-1)!$


Here $\mathrm{out}\_u(D)$ is the outdegree of a vertex, which equals the indegree $\mathrm{in}\_u(D)$, and $t(D)$ is the number of arborescences, or spanning oriented rooted trees, which for balanced digraphs turns out to be independent of the root.


I was looking for a generalization to eulerian paths with open ends. Since such paths have to be drawn without lifting the pencil, the balanced digraph on which they take place must have all balanced vertices but for two vertices $u$ and $v$ (respectively the starting and the arrival vertices), such that


$\mathrm{out}\_u(D) - \mathrm{in}\_u(D)=+1, \quad \mathrm{out}\_v(D) - \mathrm{in}\_v(D)=-1$.


Now, it seems to me that Stanley's proof works out equally well, I can't see any obvious impediment, so that one should end up with a formula like


$\epsilon\_{v,u}(D) = t\_v(D) \prod\_{v' \in V} (\mathrm{out}\_{v'}(D)-1)!$


where now, since the graph is unbalanced, $t\_v(D)$ will depend on the root. However, I couldn't find references for this, and the dedicated literature on eulerian trials seems to worried with other kinds of problems, which I have no intuition of. What do you think?



BEST theorem for Eulerian paths with open ends
The question seems to be sinking into the depths of Lethe; here is a styrofoam noodle for it.


Every Eulerian path on G can be completed to an Eulerian tour on G' which is G augmented with the edge (v,u). This correspondence is easily seen to be 1-1, so the number of desired paths on G is the formula you mention above, applied to the graph G'.


Unless I'm misunderstanding something, that should do it.


Gerhard "Email Me About System Design" Paseman, 2011.07.05


