in Graph Theory
833 views
1 vote
1 vote

Does this graph have Hamiltonian circuit?

in Graph Theory
833 views

4 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 

0
0
@Ashwani,

you are simply saying to detect if there exists cycle of 'n' length ?
0
0
@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.
0
0

1 Answer

0 votes
0 votes

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 

edited by

2 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.
0
0
@Tuhin Dutta yes you were correct ore theorem will fail here.
0
0

Related questions