TAOCP 2.3.4.2 Exercise 24
Construct a new directed graph $G'$ by replacing each arc $e_j$ of $G$ with $E_j$ parallel arcs from $\operatorname{init}(e_j)$ to $\operatorname{fin}(e_j)$.
Section 2.3.4.2: Oriented Trees
Exercise 24. [**] $$M20$$ Let $G$ be a connected digraph with arcs $e_0,e_1,\ldots,e_m$. Let $E_0,E_1,\ldots,E_m$ be a set of positive integers that satisfy Kirchhoff's law for $G$; that is, for each vertex $V$,
$$ \sum_{\operatorname{init}(e_j)=V} E_j = \sum_{\operatorname{fin}(e_j)=V} E_j. $$
Assume further that $E_0=1$. Prove that there is an oriented walk in $G$ from $\operatorname{fin}(e_0)$ to $\operatorname{init}(e_0)$ such that edge $e_j$ appears exactly $E_j$ times, for $1\le j\le m$, while edge $e_0$ does not appear. [Hint: Apply Theorem G to a suitable directed graph.]
Verified: yes
Solve time: 51s
Construct a new directed graph $G'$ by replacing each arc $e_j$ of $G$ with $E_j$ parallel arcs from $\operatorname{init}(e_j)$ to $\operatorname{fin}(e_j)$. Since $E_0=1$, there is exactly one copy of $e_0$ in $G'$. Kirchhoff's law ensures that for each vertex $V$, the number of arcs leaving $V$ in $G'$ equals the number of arcs entering $V$, so $G'$ is balanced. Moreover, $G'$ is connected because $G$ is connected, and adding parallel arcs does not disconnect the graph. By Theorem G, $G'$ possesses an Eulerian trail.
Choose an Eulerian trail of $G'$ that starts with the unique copy of $e_0$. Removing $e_0$ from this trail produces an oriented walk in $G$ from $\operatorname{fin}(e_0)$ to $\operatorname{init}(e_0)$ in which each edge $e_j$ appears exactly $E_j$ times for $1\le j\le m$, while $e_0$ does not appear. This construction satisfies all requirements. ∎