Results 1 to 7 of 7
Like Tree3Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal
  • 1 Post By Plato

Thread: Tracing an Euler's circuit

  1. #1
    Newbie
    Joined
    Mar 2017
    From
    San Marino
    Posts
    18

    Tracing an Euler's circuit

    Hi!

    The problem says: Is there a (circular) Euler's path for the following graph? If yes, trace it.
    Tracing an Euler's circuit-euler.png
    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,102
    Thanks
    2573
    Awards
    1

    Re: Tracing an Euler's circuit

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

Name:	Euler.png 
Views:	1 
Size:	3.8 KB 
ID:	37567
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,412
    Thanks
    913

    Re: Tracing an Euler's circuit

    Quote Originally Posted by MaryLaine View Post
    Hi!

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

Name:	Euler.png 
Views:	1 
Size:	3.8 KB 
ID:	37567
    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.
    Thanks from MaryLaine
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2017
    From
    San Marino
    Posts
    18

    Re: Tracing an Euler's circuit

    Quote Originally Posted by Plato View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,412
    Thanks
    913

    Re: Tracing an Euler's circuit

    Quote Originally Posted by MaryLaine View Post
    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.
    Thanks from MaryLaine
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2017
    From
    San Marino
    Posts
    18

    Re: Tracing an Euler's circuit

    Quote Originally Posted by SlipEternal View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,102
    Thanks
    2573
    Awards
    1

    Re: Tracing an Euler's circuit

    Quote Originally Posted by MaryLaine View Post
    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.
    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Does a Euler Circuit have to be a connected graph?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 29th 2014, 12:29 PM
  2. Replies: 11
    Last Post: Jul 24th 2013, 06:39 AM
  3. Replies: 0
    Last Post: May 2nd 2012, 10:14 PM
  4. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 08:18 PM
  5. Euler & Hamiltonian Circuit proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 9th 2008, 07:16 PM

/mathhelpforum @mathhelpforum