2
$\begingroup$

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.

Graph

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.