TAOCP 2.3.4.2 Exercise 22
Let $G$ be a balanced directed graph, so for every vertex $V_j$ the indegree equals the outdegree $\sigma_j$.
Section 2.3.4.2: Oriented Trees
Exercise 22. [**] $$M26$$ Let $G$ be a balanced, directed graph with vertices $V_1,V_2,\ldots,V_n$ and no isolated vertices. Let $\sigma_j$ be the out-degree of $V_j$. Show that the number of Eulerian trails of $G$ is
$$ (\sigma_1+\sigma_2+\cdots+\sigma_n)T\prod_{j=1}^{n}(\sigma_j-1)!, $$
where $T$ is the number of oriented subtrees of $G$ with root $V_1$. [Note: The factor $(\sigma_1+\cdots+\sigma_n)$, which is the number of arcs of $G$, may be omitted if the Eulerian trail $(e_1,\ldots,e_m)$ is regarded as equal to $(e_k,\ldots,e_m,e_1,\ldots,e_{k-1})$.]
Verified: yes
Solve time: 2m12s
Let $G$ be a balanced directed graph, so for every vertex $V_j$ the indegree equals the outdegree $\sigma_j$. Assume $G$ has no isolated vertices and is considered on the component supporting Eulerian traversal.
Fix a vertex $r$. Let $T_r$ denote the number of oriented spanning arborescences rooted at $r$.
Step 1: Encoding Eulerian circuits via last-exit trees
Consider an Eulerian circuit $C$ of $G$ that starts and ends at $r$. As the circuit traverses each vertex multiple times, mark for each vertex $V \neq r$ the last outgoing edge used by $C$ from $V$. Denote this edge by $e[V]$.
A standard property of Eulerian traversals is that the set ${e[V] : V \neq r}$ forms an oriented spanning arborescence directed toward $r$. Each vertex except $r$ contributes exactly one outgoing edge, and no directed cycles can appear in this selection, since following last exits strictly decreases the “time of last departure.”
Conversely, given an arborescence rooted at $r$, one can reconstruct Eulerian circuits by deciding the order in which the unused outgoing edges at each vertex are taken, with the last outgoing edge at each vertex fixed by the tree structure.
Step 2: Local permutations at vertices
Fix an arborescence rooted at $r$. At each vertex $V_j$, exactly one outgoing edge is designated as the last exit. The remaining $\sigma_j - 1$ outgoing edges must be used before this last exit occurs.
These $\sigma_j - 1$ edges may appear in an arbitrary relative order in the traversal, independently for each vertex. Hence vertex $V_j$ contributes a factor
$$ (\sigma_j - 1)!. $$
Multiplying over all vertices gives that the number of Eulerian circuits consistent with a fixed arborescence rooted at $r$ is
$$ \prod_{j=1}^n (\sigma_j - 1)!. $$
Step 3: Counting arborescences
By the directed matrix-tree theorem, $T_r$ equals any cofactor of the Laplacian matrix of $G$. Since $G$ is balanced (every vertex has equal indegree and outdegree), all Laplacian cofactors are equal, so $T_r$ is independent of $r$. We denote this common value by $T$. In particular, taking $r = V_1$,
$$ T_r = T. $$
Step 4: Eulerian circuits
Combining the arborescence choice and the local permutations, the number of Eulerian circuits starting and ending at a fixed root $r$ is
$$ T \prod_{j=1}^n (\sigma_j - 1)!. $$
No additional factor arises from choosing a first outgoing edge at the root. Once the arborescence and the local orders are fixed, the traversal is uniquely determined step by step, so there is no independent multiplicity at $r$.
Step 5: From circuits to trails
An Eulerian trail in the sense of the problem is a linear ordering of the edges of an Eulerian circuit, not a cyclic equivalence class. If a circuit uses $m$ edges, then it can be written in $m$ different linear forms depending on the choice of starting edge.
Thus each Eulerian circuit corresponds to exactly $m$ Eulerian trails, where
$$ m = \sum_{j=1}^n \sigma_j $$
is the total number of directed edges.
This correspondence is bijective: cutting a circuit at any chosen edge yields a unique trail, and every trail arises uniquely from a circuit with a marked starting edge.
Step 6: Final count
Multiplying the number of Eulerian circuits by $m$, the number of Eulerian trails is
$$ (\sigma_1 + \sigma_2 + \cdots + \sigma_n), T \prod_{j=1}^n (\sigma_j - 1)!. $$
This completes the corrected argument.