1,266 views
1 votes
1 votes

Does this graph have Hamiltonian circuit?

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

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
1 answer
2
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??
3 votes
3 votes
0 answers
3
Kabir5454 asked Jan 2, 2023
426 views
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
0 votes
0 votes
0 answers
4