Results 1 to 2 of 2

Math Help - Euler and Hamiltonian Cycle

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    178

    Euler and Hamiltonian Cycle

    Give an example of a graph that has an Euler cycle and a Hamiltonian cycle that are not identical.

    I messed around with a few examples with some loops (which I'm not sure are acceptable in Euler cycle's), but I didn't get anything.

    I understand the Euler cycles include all vertices and edges, and that Hamiltonian graphs include all vertices, but not all edges.

    So, my idea is to insert extra vertices while keeping the degrees even, since that is a requirement for Euler cycles.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    Try a odd complete graph like K_{5}. Your Hamiltonian cycle can just go around the outside, but the Euler cycle must obviously hit all edges. A simple loop is not going to work. You're going to have to have more edges than in your Hamiltonian cycle.

    Euler cycles include all edges. Vertices come along for the ride, perhaps, but that's not in the definition. Similarly, Hamiltonian cycles include all vertices. It may get all the edges as well, but that's not in the definition.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Directed Hamiltonian cycle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 14th 2010, 05:52 PM
  2. Replies: 1
    Last Post: October 13th 2010, 04:58 AM
  3. Euler cycle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 22nd 2010, 05:36 AM
  4. Euler & Hamiltonian Circuit proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 9th 2008, 08:16 PM
  5. Hamiltonian/Euler Problems (Travelling Salesman Prob)
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 19th 2006, 10:18 PM

/mathhelpforum @mathhelpforum