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.
Best Answer
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.