# Thread: Tracing an Euler's circuit

1. ## Tracing an Euler's circuit

Hi!

The problem says: Is there a (circular) Euler's path for the following graph? If yes, trace it.

I added the red numbers which indicate that there is no circular Euler's path, because c and d are two odd vertices. Is that the correct answer? I'm not sure if I've done this correctly, please help!

2. ## Re: Tracing an Euler's circuit

Originally Posted by MaryLaine
Hi!
The problem says: Is there a (circular) Euler's path for the following graph? If yes, trace it.

I added the red numbers which indicate that there is no circular Euler's path, because c and d are two odd vertices. Is that the correct answer? I'm not sure if I've done this correctly, please help!
It is not traceable because it is a di-graph (directed) otherwise it would be traceable because it has two odd vertices. You must start at one and end at the other. Do you know why?

3. ## Re: Tracing an Euler's circuit

Originally Posted by MaryLaine
Hi!

The problem says: Is there a (circular) Euler's path for the following graph? If yes, trace it.

I added the red numbers which indicate that there is no circular Euler's path, because c and d are two odd vertices. Is that the correct answer? I'm not sure if I've done this correctly, please help!
For directed graphs, you count the number of edges entering and the number exiting each vertex. It must be that every vertex except two has an equal number of edges in and out. For the other two, either they must have an equal number of ins and outs or one may have an extra in while the other an extra out.

In this example, you have B with 3x ins and only one out.

If you directed both edges go from b to c, it would have an Euler path.

4. ## Re: Tracing an Euler's circuit

Originally Posted by Plato
It is not traceable because it is a di-graph (directed) otherwise it would be traceable because it has two odd vertices. You must start at one and end at the other. Do you know why?
Because that's the rule for a circular Euler path? What do you mean that otherwise it would be traceable because it has two odd vertices? Doesn't the fact that it was two odd vertices mean that it can't be tracable?

5. ## Re: Tracing an Euler's circuit

Originally Posted by MaryLaine
Because that's the rule for a circular Euler path? What do you mean that otherwise it would be traceable because it has two odd vertices? Doesn't the fact that it was two odd vertices mean that it can't be tracable?
Good point! Yes, that is another reason why there cannot be a circular Euler path. Plato and I both commented on an Euler path in general.

6. ## Re: Tracing an Euler's circuit

Originally Posted by SlipEternal
For directed graphs, you count the number of edges entering and the number exiting each vertex. It must be that every vertex except two has an equal number of edges in and out. For the other two, either they must have an equal number of ins and outs or one may have an extra in while the other an extra out.

In this example, you have B with 3x ins and only one out.

If you directed both edges go from b to c, it would have an Euler path.
So the final answer is that this particular graph does not have an Euler's circuit? Did I understand right?

7. ## Re: Tracing an Euler's circuit

Originally Posted by MaryLaine
So the final answer is that this particular graph does not have an Euler's circuit? Did I understand right?
Yes you have that correct, you correctly understood it.
FYI The word traceable as applied to what is now called Graph Theory, goes back to the early 19th century. It simply means it is possible place a pencil at one vertex and trace the entire graph with a continuous curve crossing each edge exactly once. The general rule is that a simple graph is traceable if it has at most two odd vertices. The trace will not be a cycle if the graph as two odd vertices because the trace starts at one and ends at the other.

Also be very careful about terminology. Graph theory is so relatively new that there is little agreement or definitions, I have two well respected textbooks both contain the terms trail and path in a graph. But the are defined so that a trail in one is a path in the other and visa versa.