0
$\begingroup$

how to draw a graph with 5 vertices which is:

a)Eulerian cycle but not Hamiltonnian cycle. b)Hamiltonnian cycle but not Eulerian cycle. c)Eulerian cycle and Hamiltonnian cycle.

  • 0
    No, Eulerian cycles use all edges and return to start. Hamiltonian cycles use all vertices once each and return to start.2011-02-10

1 Answers 1

2

Two days later, this is probably worth an answer.

If your points are A, B, C, D, E then the edges AB, BC, CD, DE, EA clearly provide one of the smallest graphs which has both a Eulerian cycle and Hamiltonian cycle.

Add another edge, for example AC, and you have a graph which has the same Hamiltonian cycle but not an Eulerian cycle, since A and C have an odd number of edges.

Alternatively, the edges AB, BC, CA, AD, DE, EA, provide a Eulerian cycle but not a Hamiltonian cycle, since you can only get from B to D via A, and you cannot get back without visiting A again.

Incidentally, the neat Flash game at http://neamar.fr/Res/Icosien/ asks you to find 20 Eulerian cycle and Hamiltonian cycles for given graphs.