Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

share|improve this question
please help me answer this question – user6788 Feb 8 '11 at 12:10
3  
Write down the definitions of a Eulerian and Hamiltonian cycle and it should be quite easy with some trials. Do you remember the characterisation of Eulerian graphs ? – Klaus Feb 8 '11 at 12:17
Eulerian cycle-accessible all node once and again,compulsory cross every node while Hamiltonian cycle-node must be pass through once only ,can skip node. – user6788 Feb 9 '11 at 11:10
No, Eulerian cycles use all edges and return to start. Hamiltonian cycles use all vertices once each and return to start. – Ross Millikan Feb 10 '11 at 19:17

1 Answer

up vote 2 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.