Digraphs With Exactly One Eulerian Tour

Luz Grisales

Massachusetts Institute of Technology

Cambridge, MA 02139

USA

luzg@mit.edu

Antoine Labelle McGill University

Montréal, QC H3A 0G4

Canada

antoine.labelle@mail.mcgill.ca

Rodrigo Posada

Massachusetts Institute of Technology

Cambridge, MA 02139

USA

rposada@mit.edu

Stoyan Dimitrov University of Illinois at Chicago

Chicago, IL, 60607

USA

sdimit6@uic.edu

Abstract

We give two combinatorial proofs of the fact that the number of loopless directed graphs (digraphs) with n non-isolated vertices and with exactly one Eulerian tour up to a cyclic shift is \frac{1}{2}(n − 1)!C_{n}, where C_{n} denotes the n-th Catalan number. We construct a bijection with a set of labeled rooted plane trees and with a set of valid parenthesis arrangements.

1 Introduction and main facts

Richard Stanley has a list containing nearly 250 problems and facts, for which he asks of combinatorial proofs [1]. This work describes two such proofs for one of the problems in the list, namely Problem 199, without a known combinatorial proof. First, we recall some definitions following [2].

A (finite) directed graph (or digraph) D consists of a vertex set V = {v_{1}, …, v_{n}} and an edge set E = {e_{1}, …, e_{q}}, together with a function ϕ : V → V determining the direction of each edge. If ϕ(e) = (u, v), then we think of e as an arrow from u to v. We will call u initial vertex and v final vertex. The outdegree of a vertex v, denoted outdeg(v), is the number of edges of D with initial vertex v. Similarly, the indegree of v, denoted indeg(v), is the number of edges of D with final vertex v. A loop is an edge e for which ϕ(e) = (v, v) for some vertex v. A digraph is balanced if indeg(v) = outdeg(v) for each of its vertices v. Let [n] := {1, 2, …, n}. An oriented path in a digraph D is a sequence of vertices v_{1}, …, v_{m}, where (v_{i}, v_{i+1}) is an edge of D for each i ∈ [m−1]. If the vertices v_{1}, …, v_{m} are all different, then we call the path simple. If we have a simple path v_{1}, …, v_{m−1}, then we call the path v_{1}, …, v_{m−1}, v_{1} an oriented simple cycle.

Definition 1. An Eulerian tour in a directed graph D is a sequence of vertices a_{1}a_{2} ⋯ a_{k} such that (a_{1}, a_{2}), (a_{2}, a_{3}), …, (a_{k−1}, a_{k}), (a_{k}, a_{1}) are all the distinct directed edges of D.

Any cyclic shift a_{i}a_{i+1} ⋯ a_{k}a_{1} ⋯ a_{i−1} of an Eulerian tour is also an Eulerian tour and we will say that these tours are equivalent up to a cyclic shift.

Definition 2. A uni-Eulerian digraph is a digraph which has no isolated vertices and contains exactly one Eulerian tour (and its equivalents under cyclic shifts).

Our goal is to prove the following claim.

Theorem 3. If A_{n} is the set of loopless uni-Eulerian digraphs on the vertex set [n], then |A_{n}| = \frac{1}{2}(n − 1)!C_{n} (sequence \underline{A102693} in the OEIS [5]), where C_{n} = \frac{1}{n+1} \binom{2n}{n} denotes the n-th Catalan number.

For example, |A_{3}| = 5. Indeed, there are two such digraphs that look like triangles and three that consist of two 2-cycles with a common vertex (see Figure 1). The related OEIS sequence, \underline{A102693}, was created by Richard Stanley. As a reference, he points out to an unpublished work of him. Thus, we can assume that Theorem 3 was first proved there.

It is not difficult to show that every uni-Eulerian graph must be connected and balanced [2, Theorem 10.1]. The BEST theorem that we recall below gives us a formula for the total number of Eulerian tours in a digraph. In order to understand this result, one should be familiar with the term oriented tree (see Figure 2). An oriented tree with root v is a finite digraph T with v as one of its vertices, such that there is a unique directed path from any other vertex of T to v. This means that the underlying undirected graph (after we erase all the arrows of the edges of T) is a tree.

1 2 3 1 3 2 1 3 2 2 1 3 3 2 1

Figure 1: The five digraphs with three vertices and a unique Eulerian tour.

1 2 4 3 5 6

Figure 2: Example of an oriented tree.

Theorem 4 ([2], Theorem 10.2). Let D be a connected balanced digraph with vertex set V. Fix an edge e in D and let v be the initial vertex of that edge. Let τ(D, v) denote the number of oriented (spanning) subtrees of D with root v, and let ϵ(D, e) denote the number of Eulerian tours of D starting with the edge e. Then

ϵ(D, e) = τ(D, v) ∏_{u∈V}(outdeg(u) − 1)!

Corollary 5 (from Theorem 4). A digraph D ∈ A_{n} if and only if 1. For every vertex v, D has exactly one oriented (spanning) subtree with root v.

2. The outdegree of an arbitrary vertex of D is 1 or 2.

Note that if the two conditions of Corollary 5 hold, then ϵ(D, e) = 1 for every edge e of the digraph D and thus D has a unique Eulerian tour. Using Corollary 5, we will characterize the digraphs in A_{n} by two other conditions that will be used later. Lemma 6. A digraph D ∈ A_{n} if and only if

i) There exists a unique oriented simple path between any two vertices of D.

ii) Every vertex of D is part of exactly one or two simple oriented cycles. Corollary 7. If D ∈ A_{n}, then no pair of cycles in D have an edge in common.

Proof. Assume C_{1} and C_{2} are two different cycles in D, which have the edge (u, v) in common. Then, we will have at least two oriented paths from v to u in D—one following C_{1} and another one following C_{2}. This is a contradiction with Corollary 5.

Proof of Lemma 6. [first part: D ∈ A_{n} ⟹ conditions i) and ii)] Let D ∈ A_{n}. Let u and v be two arbitrary vertices in D. By condition (1) of Corollary 5, there exists exactly one oriented spanning subtree T_{u} of D with root u. We know that v has to be a vertex of T_{u} and that there exists a unique simple path P from v to u in T_{u}, which is a simple oriented path in D. Assume that there exists another path P′ ≠ P between v and u in D. Begin from v and follow P′. Let f′ be the first edge in P′, which is not part of P and let f be the edge in P with the same initial vertex as f′. If you delete f from T_{u} and add f′ to it, you will obtain a graph T′_{u}. One can easily see that T′_{u} is an oriented spanning subtree of D, different from T_{u} (see Figure 3). This is a contradiction. Thus, we showed that condition i) holds.

By Corollary 7, we know that no pair of cycles in D have an edge in common. Therefore, Corollary 5 implies that each vertex of D can be part of at most two simple oriented cycles since its outdegree is 1 or 2. It remains to show that each vertex of D is part of at least one such cycle. Let v be an arbitrary vertex of D and let (u, v) be an edge of D (such an edge exists since the indegree of v is 1 or 2). We showed that there is a unique oriented simple path between v and u. This path together with the edge (u, v) forms a simple oriented cycle. Thus condition ii) holds.

12345678911 12 13 10 f′ f

Figure 3: The tree T_{u} in the first part of the proof of Lemma 6; u = 1, v = 11, P = 11, 9, 6, 5, 1, P′ = 11, 9, 6, 2, 1, f′ = (6, 2) and f = (6, 5). Delete f and add f′ to obtain another tree T′_{u}.

[second part: conditions i) and ii) ⟹ D ∈ A_{n}] Take a digraph D for which conditions i) and ii) hold. We have to show that conditions (1) and (2) from Corollary 5 also hold. Let v be an arbitrary vertex of D. Condition ii) implies that outdeg(v) ≥ 1. We will show that outdeg(v) < 3. By Corollary 7 no edge of D can be part of two different simple cycles. Assume that outdeg(v) ≥ 3 and let (v, u_{1}), (v, u_{2}) and (v, u_{3}) are three different edges of D.

We know that there exist simple paths between u_{i} and v, for i = 1, 2, 3. Thus, v participates in simple cycles through u_{i}, for i = 1, 2, 3 and no two of these simple cycles share and edge. Therefore these three cycles are different. This is a contradiction with condition ii).

It remains to show that condition (1) from Corollary 5 holds. Take an arbitrary vertex v of D. We have a unique oriented simple path from each of the other vertices of D to v. Take the union of these paths. The graph that you will obtain is an oriented spanning subtree T_{v} of D with root v. Assume that there exists another such subtree T′_{v}. Then, since T_{v} ≠ T′_{v}, we must have a vertex w in D, for which the unique oriented path from w to v in T′_{v} is different from the unique oriented path from w to v in T_{v}. These are two different oriented paths from w to v in D, which is a contradiction.

2 Bijection with a set of labeled rooted plane trees

We will construct a bijection between the digraphs in A_{n} and a set of labeled rooted plane trees on n + 1 vertices. Let U_{n} be the set of the unlabeled rooted plane trees with n + 1 vertices. It is well-known that |U_{n}| = C_{n} (see [3, Theorem 1.5.1]). Let L_{n} be the set of the labeled rooted plane trees with n+1 vertices such that the root is always labeled as 0 and the left-most child of the root is always labeled as 1. We have |L_{n}| = (n − 1)!|U_{n}| = (n − 1)!C_{n}. Finally, let L′_{n} ⊂ L_{n} be the set of the labeled trees in L_{n}, such that the vertex 2 is in the subtree with root 1.

First, we define a map f over L_{n}, such that f(L′_{n}) = L_{n} \ L′_{n} and f(f(T)) = T, i.e., an involution. This shows that |L′_{n}| = \frac{|L_{n}|}{2} = |A_{n}|. Then, we define a map g : L′_{n} → A_{n}, which is shown to be a bijection. Below, we will denote by T_{(x,j)} the j-th child (from left to right) of the vertex x of a tree T ∈ L_{n}.

Definition 8. Let f : L_{n} → L_{n} be a map, which switches the places of the subtree with root 1 (excluding 1) and the subtree with root 0 (excluding 0 and the subtree with root 1), for every tree in L_{n} (see Figure 4). Formally, if T ∈ L_{n}, then f(T) has the following properties. For every j ≥ 1:

• If the vertex v is the (j + 1)-th child of the vertex 0 in T, then v is the j-th child of vertex 1 in f(T), i.e., T_{(0,j+1)} = f(T)_{(1,j)}.

• If the vertex v is the j-th child of the vertex 1 in T, then v is the (j + 1)-th child of vertex 0 in f(T), i.e., T_{(1,j)} = f(T)_{(0,j+1)}.

• All the other directed edges are left the same for both trees, i.e., T_{(u,j)} = f(T)_{(u,j)} for u ∉ {0, 1}.

It is easy to check that f(L′_{n}) = L_{n} \ L′_{n} and f(f(T)) = T, i.e., f^{−1} = f.

Definition 9. Let g : L′_{n} → A_{n} be a map, such that if T ∈ L′_{n}, g(T) = D′ is a digraph with V (D′) = [n] and E(D′), such that if x is a vertex of T with r children, then:

\begin{matrix}T \\ 2 \\ 3 \\ 6 \\ 5 \\ 4 \\ 1 \\ 0 \\ f(T) \\ 6 \\ 4 \\ 5 \\ 3 \\ 2 \\ 1 \\ 0 \end{matrix}

Figure 4: Example of the action of the map f.

1. For every i ∈ [1, r), (T_{(x,i)}, T_{(x,i+1)}) ∈ E(D′).

2. If x = 0, then (T_{(x,r)}, T_{(x,1)}) ∈ E(D′).

3. If x ≠ 0, then (T_{(x,r)}, x) ∈ E(D′) and (x, T_{(x,1)}) ∈ E(D′).

\begin{matrix}T \\ 2 \\ 3 \\ 7 \\ 9 \\ 8 \\ 6 \\ 5 \\ 4 \\ 1 \\ 0 \\ g(T) \\ 2 \\ 7 \\ 9 \\ 8 \\ 3 \\ 6 \\ 5 \\ 4 \\ 1 \end{matrix}

Figure 5: Example of the action of the map g.

Lemma 10. For every T ∈ L′_{n}, g(T) ∈ A_{n}, i.e., g(T) has exactly one Eulerian tour.

Proof. First, note that every vertex x of g(T) belongs to one or two cycles:

• The cycle where x and its parent from T both belong.

• In case x has children in T, the cycle formed by x and its children in g(T).

By Lemma 6, it remains to show that there exists a unique oriented simple path between any two vertices of g(T), for arbitrary T ∈ L′_{n}. To see this, observe that if (v, w) ∈ E(T) and v, w ≠ 0 or if both v and w are children of the root 0 in T, then we have a unique oriented simple path between v and w in g(T), which is part of a single cycle. For instance, the edge (1, 3) in the graph T shown at Figure 5 corresponds to the oriented simple path 1273 in g(T), whereas the path 514 in g(T) corresponds to the pair of children 4 and 5 of the root of T.

We will show that since we have a unique non-oriented path P between any two vertices u and v in T, where u, v ≠ 0, we will also have a unique oriented simple path P^{or} between u and v in g(T). If the vertex 0 is part of P, then we must have vertices h_{1} and h_{2} in T, such that the edges (h_{1}, 0) and (0, h_{2}) are part of P (since v, w ≠ 0). Hence, h_{1} and h_{2} are two children of the root 0. Replace the edges (h_{1}, 0) and (0, h_{2}) of P with the unique oriented simple path between h_{1} and h_{2} in g(T). Replace all the other edges of P with the corresponding oriented simple paths to obtain P^{or}. For example, the unique path P between 3 and 8 in the graph T on Figure 5 is comprised of the edges (3, 1), (1, 7), (7, 8). The oriented paths corresponding to these edges are 31, 127 and 798, respectively. The union of these paths, namely 312798, gives the unique path P^{or} between 3 and 8 in g(T). Another example is the path 71056 in T, which transforms to the path 731456 in g(T).

Lemma 11. For every digraph D ∈ A_{n}, there exists a unique labeled tree T ∈ L′_{n}, for which g(T) = D. i.e., g has an inverse.

Proof. Let D be an arbitrary digraph in A_{n}. Below, we describe the procedure buildSubtree(r, C, T, D) that will be used to obtain the tree T, for which g(T) = D. The first argument, r, is a vertex in D and the second argument, C, is a cycle in D that contains r.

1 buildSubtree(r, C, T, D):
2  For each v ∈ C:
3  if v ≠ r:
4  add an edge (r, v) to E(T).
5  if v is part of a cycle C_{1} ≠ C:
6  buildSubtree(v, C_{1}, T, D).

Initially, let T be an empty tree with n + 1 vertices, i.e., let V (T) = {0, 1, …, n} and let E(T) = ∅. Take the vertex with label 1 in D. By Lemma 6, this vertex belongs to one or two simple oriented cycles. We consider each case separately.

Suppose that the vertex belongs to one such cycle and let C denotes this cycle. Then, run buildSubtree(1, C, T, D) and add an edge (0, 1) to E(T). One can easily show that the resulting graph, T, is a tree in L′_{n}. First, T is connected since the execution of buildSubtree(1, C, T, D) will reach every vertex of D and connect this vertex to an already reached vertex. In addition, if we have two different paths between two vertices u and v of T, then we will be able to find two simple oriented paths between u and v in D, which contradicts Lemma 6. Finally, n ≥ 2 and the only vertex of T, which is not in the subtree with root 1, is the vertex 0. Thus, 2 is in that subtree and T ∈ L′_{n}.

Now, suppose that the vertex 1 belongs to two different cycles C_{1} and C_{2}. Then, find the unique oriented simple path between 1 and 2 in D. This path has to have an edge in common with either C_{1} or C_{2}, but not with both. Otherwise, we will have a contradiction with Corollary 7. Without loss of generality, let this be C_{2}. Execute buildSubtree(0, C_{1}, T, D). The graph T, obtained at the end, will be a tree in L′_{n} (see Figure 6).

\begin{matrix}g(T) \\ 1 \\ 5 \\ 2 \\ C_{2} \\ 4 \\ 6 \\ 3 \\ C_{1} \\ T \\ 1 \\ 5 \\ 2 \\ 3 \\ 6 \\ 4 \\ 0 \end{matrix}

Figure 6: Example of the action of the inverse map g^{−1}.

Lemmas 10 and 11 imply that the map g is a bijection.

3 A bijection with parentheses arrangements

In this section, we give a second combinatorial proof of Theorem 3, via a bijection between the digraphs in A_{n} and a set of valid parentheses arrangements. Suppose that you have n pairs of opening and closing parenthesis, such that the two parenthesis in each pair are labeled with the numbers in [n]. A valid labeled parentheses arrangement is an ordering of these 2n parenthesis, such that we cannot have two interlaced pairs, e.g., (_{i}(_{j})_{i})_{j} for some i, j ∈ [n]. A valid unlabeled parentheses arrangement is a sequence of unlabeled opening and closing parentheses that can be obtained by forgetting the labels of a valid labeled arrangement. One can easily check that a sequence of n opening and n closing parentheses is valid if and only if every prefix of the sequence has at least as many opening parentheses as closing parentheses. The number of valid arrangements of n unlabeled pairs of parentheses is C_{n} [3, Theorem 1.5.1]. Thus the number of such arrangements for labeled pairs is n!C_{n}.

To construct a bijection with the set of digraphs A_{n}, let us first note that one can assume that all vertices of a uni-Eulerian digraph have indegree and outdegree 2, provided that we allow digraphs with loops.

Lemma 12. If B_{n} is the set of all uni-Eulerian digraphs on the vertex set [n] (possibly with loops) with all vertices of indegree and outdegree 2, then |B_{n}| = |A_{n}|

Proof. Given a digraph D in A_{n}, Corollary 5 implies that all vertices have outdegree 1 or 2 and the same indegree. Moreover, the single Eulerian tour of D passes exactly once through each vertex of outdegree 1. Hence, adding a loop to every vertex of outdegree 1 gives an element of B_{n}.

Conversely, given a digraph D′ in B_{n}, deleting all loops gives an element of A_{n}. Indeed, the loopless digraph still has a unique Eulerian tour, which is just the tour for D′ without the loops (the uniqueness follows because adding back loops must give an Eulerian tour for D′). These two maps are inverses of each other and thus give a bijection between A_{n} and B_{n}.

Now, let B_{n}^{∗} be the set of digraphs in B_{n} together with an identified edge. Since all digraphs in B_{n} have 2n edges, we have |B_{n}^{∗}| = 2n|B_{n}| = 2n|A_{n}|. We will give a bijection between B_{n}^{∗} and the set of valid arrangements of n labeled pairs of parentheses, which will show that 2n|A_{n}| = n!C_{n}, that is, |A_{n}| = \frac{1}{2}(n − 1)!C_{n}.

Theorem 13. There exists a bijection between B_{n}^{∗} and the set of valid arrangements of n labeled pairs of parentheses.

Proof. [first part: Digraphs in B_{n}^{∗} → valid parentheses arrangements].

Let D be a digraph in B_{n}^{∗} with identified edge e. We define a parentheses arrangement h(D) as follows:

Following the unique Eulerian tour of D, starting at e, open the i-th pair of parentheses when you pass through the vertex i for the first time and close the i-th pair of parentheses when you pass through the vertex i for the second time (see Figure 7 below).

2 1 3

Figure 7: The digraph in B_{3}^{∗} (with the edge 2 → 1 being identified) that yields the string (_{1})_{1}(_{2}(_{3})_{3})_{2}

To show that the resulting string of parentheses is valid, we have to show that we cannot have two interlaced pairs of parentheses, e.g.,

⋯ (_{i}⋯ (_{j}⋯)_{i} ⋯)_{j} · · · .

In other words, the unique tour cannot have the form

i ⟶^{a} j ⟶^{b} i ⟶^{c} j ⟶^{d} i

for some walks a, b, c, d. But this is clearly impossible, because otherwise we would have a second Eulerian tour i ⟶^{a} j ⟶^{d} i ⟶^{c} j ⟶^{b} i.

[second part: Valid parentheses arrangements → digraphs in B_{n}^{∗}] Given a valid parentheses arrangement w = (_{x}⋯)_{y}, we obtain a digraph h^{−1}(w) ∈ B_{n}^{∗} by putting an edge between the corresponding vertices of any pair of consecutive parentheses (from the first parenthesis to the second) and an edge from y to x. The identified edge is y → x.

Clearly, every vertex in h^{−1}(w) has indegree and outdegree 2 and that there exists an Eulerian tour T, given by the order of the parentheses’ labels in w. Hence, we just have to show that T is the unique Eulerian tour of h^{−1}(w). Let i ∈ [n] and let

w = ⋯?_{ℓ}(_{i}(_{j}⋯)_{i}?_{k} ⋯,

where ? represents either a closing or an opening parenthesis (if (_{i} and )_{i} are consecutive we let j = i, if (_{i} is the first parenthesis of w we let ℓ be the label of the last one and if )_{i} is the last parenthesis, we let k be the label of the first one). We have to show that if an Eulerian tour enters the vertex i for the first time from ℓ, this tour must exit the vertex i towards j and not k. Indeed, if this is true for all i, then the Eulerian tour is entirely determined by its first edge. Thus, this tour and T are equal up to a cyclic shift. Suppose, for the sake of contradiction, that there exists an Eulerian tour T′ of h^{−1}(w), which exits i towards k, after entering i for the first time, through ℓ.

Note that, by the properties of valid parentheses arrangements, the two parentheses corresponding to any vertex v ≠ i are either both between (_{i} and )_{i} (then we will say that v is of type A) or both outside (type B). Clearly, all edges of the graph h^{−1}(w) with initial vertex of type A (respectively B) have a final vertex either i or of type A (respectively B), so the only way to go from a vertex of type A to a vertex of type B is through i and vice-versa. Therefore, since k is of type B, we must re-enter i in T′ through a vertex of type B, in order to access vertices of type A. The only way to do so, however, is through the edge ℓ → i, which was already used in T′. This is a contradiction, so the uniqueness of the Eulerian tour is proved. The two described maps h and h^{−1} are obviously inverses of each other, so the proof is complete.

4 Acknowledgments

We are thankful to Jan Kynčel for the suggestions in the mathoverflow post related to the considered problem [4].

References

[1] R. P. Stanley, “Bijective proof problems.”, 2009, https://klein.mit.edu/~rstan/bij.

   pdf.

[2] R. P. Stanley, Algebraic Combinatorics. Springer, 2013.

[3] R. P. Stanley, Catalan Numbers. Cambridge University Press, 2015.

[4] J. Kynčel, mathoverflow answer, 2020, https://mathoverflow.net/questions/
   366383/digraphs-with-exactly-one-eulerian-tour.

[5] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2020, https://

   oeis.org.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05C20. Keywords: bijective proof, directed graph, Eulerian tour, Catalan number, labeled tree.

(Concerned with sequence \underline{A102693}.)

Received May 26 2021; revised versions received June 4 2021; August 24 2021; February 10 2022. Published in Journal of Integer Sequences, March 27 2022.

Return to Journal of Integer Sequences home page.