# Show that there is an Euler Tour in a digraph where the in-degree and out-degree is 2

Draw a simple connected directed graph with 8 vertices and 16 edges such that the in-degree and out-degree of each vertex is 2. Show that there is a single, non-simple, cycle in the graph that includes all the edges in the graph.

So I began with a graph with the given properties to see what is actually going on. And I can see that yes, there is in fact an Euler tour and it is non-simple.

Then I show that we can include every edge in a list of cycles since there are degrees of two.

In graph $G$, every vertex has an even degree where the degree is exactly two, then there exists a list of cycles $C_1, C_2, ..., C_m$ such that every edge appears in exactly one cycle. \newline

Proof: Choose a maximal list of cycles $C_1, ..., C_m$ which have disjoint edge sets. Suppose that some component $H$ of $G - (\cup_{i = 1}^m E(C_i) )$ has at least one edge. Since every vertex of $G$ has an even degree, it follows that every vertex in $H$ has an even degree. Since $H$ is connected with $E(H)\neq \emptyset$, then it follows that every vertex of $H$ has degree $\ge$ 2. But then the proposition shows that $H$ contains a cycle, contradicting the choice of $C_1, ... C_m$. Thus $\cup_{i = 1}^m E(C_i) = E(G)$ and every edge occurs exactly once in $C_1, ... C_m$, as stated.

This works for simple graphs, but I need to change it so that it works with digraphs... And this is where I get stuck. At this point, I'm not even sure if I'm going the right direction. Any assistance is appreciated, thank you.

• Do you assume weak or strong connectivity of the digraph? – Nick Peterson Aug 5 '13 at 19:05
• I'm not sure. We haven't discussed the strength of connectivity. I only have the question that you see to work with. – Evan Aug 5 '13 at 19:26

Step 1: Start with any vertex $v$ and start moving along unused edges until you return to $v$. Observe that from the condition on the in- and out-degrees, whenever you enter a vertex you are going to be able to go out.
Step 2: Assume you got such a cycle but it didn't use all edges. Let $w$ be a vertex in the cycle used that has an edge that has not been used. Start a cycle from $w$ and using edges that have not been used. Again, this can be done because for every edge not used, incident in a vertex $a$, there is going to be a not used edge coming out of $a$. Insert that new cycle to the old one, in $w$. Repeat this step until all edges are used.