833 views

Does this graph have Hamiltonian circuit? There is another way to check for Hamiltonian graph

If we are able to make degree of each vertex in graph exactly 2 by deleting some of the edges, then graph is Hamiltonian

Delete edge BD and DC, we will get a 2-regular graph, hence Hamiltonian

@Ashwani,

you are simply saying to detect if there exists cycle of 'n' length ?
@joshi_nitish

Yes..we are trying to get a Hamiltonian circuit and we know a Hamiltonian circuit is cycle which contains all the vertices exactly once and some of the edges can be skipped.

A graph is Hamiltonian if Hamiltonian circuit exists.

It has hamiltonian circuit

By Dirac's Theorem

deg(u) $\geq \left \lfloor \frac{n}{2} \right \rfloor$

here $\left \lfloor \frac{n}{2} \right \rfloor = \left \lfloor \frac{5}{2} \right \rfloor=2$

deg(A)= 2

deg(B)=3

deg(C)=3

deg(D)=4

deg(E)=2

By definition: A closed walk which traverse all the vertices of graph exactly onces( except starting and ending) has hamiltonian circuit.

by

why haven't you considered deg(a+e) = 4 which is violating ore's theorem? Although it is not a necessary condition that's why even it doesn't satisfy then also there exists a hamiltonian circuit.
@Tuhin Dutta yes you were correct ore theorem will fail here.