# discreat math 1

Printable View

• Jun 25th 2007, 12:56 AM
kashif
discreat math 1
a) Determine whether the following graph has an Euler circuit. If it exists then write the circuit, if not then write the reason.
b) Determine whether the following graph has a Hamiltonian circuit. If it exists then write the circuit, if not then write the reason.
• Jul 8th 2007, 06:24 PM
le_su14
Quote:

Originally Posted by kashif
a) Determine whether the following graph has an Euler circuit. If it exists then write the circuit, if not then write the reason.
b) Determine whether the following graph has a Hamiltonian circuit. If it exists then write the circuit, if not then write the reason.

a)The graph has an Euler circuit : a,b,c,d,e,g,c,h,e,f,h,b,f,a .

b)It doesn't have a Hamilton circuit . Because :

A Hamilton circuit is the longest circuit .
It never contains other circuits. (1)
It always contains every edges next points x that d(x) = 2 . (2)

If having a Hamilton circuit ,the Hamilton will contains eg , gc , cd and ed (2) . But these 4 edges create a circuit . Arcording to (1) , there is a conflict .

So , the graph has no a Hamilton circuit .