Results 1 to 12 of 12
Like Tree2Thanks
  • 1 Post By Prove It
  • 1 Post By Prove It

Math Help - Euler Circuit, do I have to use all edges and vertices?

  1. #1
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Euler Circuit, do I have to use all edges and vertices?

    Hello again everyone!

    With the Euler's Circuit, do I have to use all vertices and edges?

    The question is: find a Euler's circuit in figure 11.44

    Euler Circuit, do I have to use all edges and vertices?-euler-circuit.png
    I counted the degrees and they are all of even numbers. But I can't find my way finding a euler circuit using everything.

    But I did this, I just made a subgraph into a euler's circuit.

    Euler Circuit, do I have to use all edges and vertices?-euler-circuit-1.png

    Eulerís Theorem 1
    If a graph has any vertices of odd degree, then it CANNOT have an EULER CIRCUIT.
    AND
    If a graph is connected and every vertex has even degree, then it has AT LEAST ONE EULER CIRCUIT (usually more).
    <--- when it says at least one euler circuit, so there are more circuits, but does it use all vertices and edges or not?

    Thanks so much!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,402
    Thanks
    1291

    Re: Euler Circuit, do I have to use all edges and vertices?

    For an Euler Circuit, you are required to use each edge exactly once and end up at the node you started with. You may pass through any node as many times as needed.
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Euler Circuit, do I have to use all edges and vertices?

    I just found out something.

    a --> b --> c --> g --> k --> j --> i --> h -->d --> e --> i --> f -->j --> g --> b --> f --> e --> b --> d --> a

    I visited some vertices twice but I believe I only passed each edge once.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Euler Circuit, do I have to use all edges and vertices?

    Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Euler Circuit, do I have to use all edges and vertices?

    Quote Originally Posted by Prove It View Post
    For an Euler Circuit, you are required to use each edge exactly once and end up at the node you started with. You may pass through any node as many times as needed.
    But then, can I skip some vertices, like not use all vertices? like a subgraph? Still passing edges once though but only within that subgraph.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,402
    Thanks
    1291

    Re: Euler Circuit, do I have to use all edges and vertices?

    Quote Originally Posted by jpab29 View Post
    But then, can I skip some vertices, like not use all vertices? like a subgraph? Still passing edges once though but only within that subgraph.
    How can you go through every edge without going through every vertex?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Euler Circuit, do I have to use all edges and vertices?

    hmm... i can't do this?Euler Circuit, do I have to use all edges and vertices?-euler-circuit-1.png
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,402
    Thanks
    1291

    Re: Euler Circuit, do I have to use all edges and vertices?

    You have clearly missed all the edges inside...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Euler Circuit, do I have to use all edges and vertices?

    So that means I can't do it if i don't use all the edges.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Euler Circuit, do I have to use all edges and vertices?

    Going back to my question:

    With the Euler's Circuit, do I have to use all vertices and edges?

    Vertices: you answered i can go through it as many times as I want.
    Edges: you said that I missed the edges inside.

    So in my understanding to have a Euler's circuit is to use all the edges in the graph, and not omit any edges like it would be a subgraph.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,402
    Thanks
    1291

    Re: Euler Circuit, do I have to use all edges and vertices?

    That is correct
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Euler Circuit, do I have to use all edges and vertices?

    Okay thanks so much! I found a way around it and i'm erasing the wrong one. Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Vertices and Edges
    Posted in the Geometry Forum
    Replies: 2
    Last Post: March 23rd 2010, 02:16 PM
  2. Components, edges, and vertices
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 1st 2009, 10:35 AM
  3. Edges and vertices of a solid
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 6th 2009, 07:02 AM
  4. Replies: 5
    Last Post: June 22nd 2008, 10:20 PM
  5. Eulerian graph with even vertices and odd edges
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 23rd 2007, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum