Thread: 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.

Try a odd complete graph like 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.