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.
a)The graph has an Euler circuit : a,b,c,d,e,g,c,h,e,f,h,b,f,a .
Originally Posted by kashif
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 .