# BEST theorem for Eulerian paths with open ends

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?

-
Try drawing a line segment between the two unbalanced vertices, and then use the previous result. Gerhard "The Shortest Distance Between Results..." Paseman, 2011.07.01 –  Gerhard Paseman Jul 1 '11 at 20:21

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

-
It seems to work. Then my formula is wrong, since deletion-contraction formulas for $t_v(G')$ imply that I'm forgetting a piece; I'll have to make up my mind where Stanley's proof fails for unbalanced digraphs. –  tomate Jul 6 '11 at 8:21
Sleep on it for a night. If it still doesn't work out tomorrow, try a new question to ask for help with the sticky bits. Gerhard "Email Me About System Design" Paseman, 2011.07.06 –  Gerhard Paseman Jul 6 '11 at 8:30
Wait, now I see why this is wrong. It's not true that the correspondence is 1-1. Eulerian paths on G with open ends are 1-1 with those eulerian cycles on G+(v,u) whose final edge is (v,u)! But internal cycles in an eulerian cycle can be walked in any desired order! I'm more and more convinced that my guess is correct. –  tomate Jul 22 '11 at 13:34
I am not sure what you are counting. The edge removal does matter if you are counting a traversal of an Eulerian tour with a given start/endpoint. If you consider two traversals equivalent if the sequence of edges traveled differs by a cyclic permutation, then I think the (set of) equivalence classes of traversals is equinumerous with the paths. If you make clear what is being counted (I thought it was equiv. classes), then I may adjust my answer as needed. Gerhard "Ask Me About System Design" Paseman, 2011.07.22 –  Gerhard Paseman Jul 22 '11 at 23:54