Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Eulerian and hamiltonian questions

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    212

    Eulerian and hamiltonian questions

    (a) For what values of
    n (where n => 3) does the complete graph Kn have an Eulerian
    tour? Justify your answer.
    (b) For what values of
    n (where n => 3) does the complete graph Kn have a Hamiltonian

    cycle? Justify your answer.

    I have no idea what these questions mean. Are the questions referring to a particular graph that I should have or are they just general questions? Please help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    The complete graphs Kn are those simple undirected graphs where all the vertices have exactly one edge connecting them to each of the other vertices. That is, every distinct pair of vertices is connected with one edge.

    Does this help?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2008
    Posts
    212
    Is the answer to a) all of them and the answer to b) none of them? Or am I completely off? I still don't know how you can tell.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    No. I think some will have them, others won't. What is the criteria, you might ask? Look here for Euler tours, and here for Hamiltonian cycle. How can you do this sort of counting for the complete graphs Kn?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2008
    Posts
    212
    I know the definitions for the two kinds but I still can't see the answers. Obviously when n = 3 there is a eulor tour, but how do I know for the others? I'm so confused.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    What are the necessary conditions that a graph have an Euler tour? Hamiltonian cycle?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2008
    Posts
    212
    For a eulor tour, the path meets each edge only once and starts and finishes on the same vertex. For the hamiltonian cycle the path meets each vertex only once and starts and finishes at the same vertex...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Your first definition is for the Euler cycle, not the Euler tour. The tour doesn't have to start and end on the same vertex, although it is allowed to do so. So an Euler cycle is an Euler tour, but not necessarily vice versa. Your Hamiltonian cycle definition is correct.

    But what you need now are practical ways to determine if a graph has an Euler tour or a Hamiltonian cycle. How about a numerical criterion?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by Ackbeet View Post
    Your first definition is for the Euler cycle, not the Euler tour. The tour doesn't have to start and end on the same vertex, although it is allowed to do so. So an Euler cycle is an Euler tour, but not necessarily vice versa. Your Hamiltonian cycle definition is correct.

    But what you need now are practical ways to determine if a graph has an Euler tour or a Hamiltonian cycle. How about a numerical criterion?
    An Euler tour and an Euler cycle/circuit are the same thing.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    In graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. - wiki
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jul 2008
    Posts
    212
    Well there isn't one specified aside from the n >= 3 do I just go up to n = 12?

    Sorry just letting you know its 4am in the morning where I am and I'm trying to get this done now so sorry if I ask dumb questions!!!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Ah, I see.

    An Eulerian path, Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. . .

    An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph ...

    So, path = trail = walk, and cycle = circuit = tour.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by Ackbeet View Post
    In graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. - wiki
    Yes, but tour means cycle.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by Ackbeet View Post
    Ah, I see.

    An Eulerian path, Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. . .

    An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph ...

    So, path = trail = walk, and cycle = circuit = tour.
    Exactly.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    You can have an Euler tour if and only if the graph is connected and all vertices have even degree. So which complete graphs satisfy this requirement?

    For the Hamiltonian, I think you can see that all you really need is the ability to come back on yourself. Hence, K1 and K2 don't fit the bill. However, K3 on up work because you can just traverse the "outside", so to speak, and end up where you started.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Proof of being Eulerian
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 13th 2011, 02:40 AM
  2. Replies: 1
    Last Post: October 13th 2010, 03:58 AM
  3. [SOLVED] Eulerian graphs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 13th 2010, 10:40 AM
  4. Eulerian graph with even vertices and odd edges
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 23rd 2007, 03:12 PM
  5. eulerian graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2007, 03:41 AM

Search Tags


/mathhelpforum @mathhelpforum