Using the Diracs condition decide whether G4 is Hamiltonian

Using the Dirac\'s condition, decide whether G_4 is Hamiltonian or not.

Solution

Answer :

Drac\'s theorem : A sufficient condition for a graph to be Hamiltonian .

A simple graph witn n vertices ( n > 2 ) is Hamiltonian if the degree of the vertex is atleast n/2.

But for the given graph has n = 8 vertices ,

some of the vertices have degree ( deg(1) =deg(2)=deg(3) =deg(6)=deg(7)= deg(8) = 2 ) which is not at least 8/2 = 4.

hence using Dirac\'s theorem , the given graph G4 is not Hamiltonian