Tags: #theorem

Statement

Let $G$ be a directed graph such that the indegree of any vertex is equal to its outdegree. Then, the number of Eulerian cycles on this graph is

Proof

We shall give a bijection between Eulerian cycles and pairs of arborescences rooted at $r$ and tuples $({\pi }_v{)}_{v\in V}$ of permutations ${\pi }_v\in S_{|\mathrm{indeg}(v)-1|}$.

Given an Eulerian cycle $c=(e_1,\dots ,e_n)$

1. Fix an edge $e$ and let $r$ be the endpoint of $e$
2. For all $v\ne r$, mark the first edge of $c$ that enters $v$
   • This will give an arborescence rooted at $r$
3. For all $v\in V$, let $E_v$ be the set of edges that go to $v$ that is not marked or $e$
4. We set ${\pi }_v$ to be the permutation of $E_v$ given by the order of their appearance in $c$

Let us verify that the marked edges form an arborescence. In particular, note that there are $v-1$ marked edges and for every vertex $v\ne r$, there is one edge entering $v$. Furthermore, it has no directed cycles. If there was, then it cannot contain $r$. Additionally, there is a path from $r$ to the cycle. The vertex at which $r$ reaches the cycle will have two in-edges, a contradiction.

Thus, these form an arborescence and yields us the pair.

Given a pair of an arborescence and these permutations, we shall iteratively build the walk starting from the end:

1. start with the edge $e:i\to r$
2. Pop the last edge of $E_i$ and record it (from the end)
3. Set $e$ to be this popped edge
4. iterate this process
5. After all $E_i$'s are empty, then follow the edges in the arborescence