Graph theory

Question

Does this graph have Hamiltonian circuit?

Comments

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.

Answer 1

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.

ADECBA is the desired circuit 

Comments

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.