Hamiltonian Graph

Question

A complement of a cyclic graph on 5 vertices , has an Hamiltonian circuit . (True/False)

Comments

yes, true!

cycle graph with 5 vertices is self complementary, therefore complement of $C_5$ is also $C_5$ and therefore it will also have Hamiltonian cycle.

---

I think it will be K5

---

can complement of $C_5$ be ever $K_5$ ?

---

yeah,you are right,my mistake

---

can i say like complement of c5 has vertex degree 2 ( max degree - degree of cycle graph with 5 vertex =4-2) which is even , from theorem its hamilton ckt

---

@joshi_nitish

I am not talking about Cycle graph, I am asking Cyclic Graph.

  A cyclic graph is a graph containing at least one graph cycle. 

---

@Pawan Kumar 2

This graph is Eulerian , but NOT Hamiltonian.

Here, deg(v) >= floor(n/2) = 2 , But , it is not hamiltonian.

In formula for Dirac's theorem , we don't have floor.

Dirac's Theorem    Let G be a simple graph with n vertices where n ≥ 3 If deg(v) ≥ n/2  for each vertex v, then G is Hamiltonian.

             Ref:  http://personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/eulerGraph.htm                                                                                         

---

yes  mam I've corrected it now thanks .. In hamiltonian ckt , every vertex is traversed once and traversal starts and ends at same node .. but thats not the case with hamiltonian path....But still Dirac's and Ore's theorem used for Hamiltonian Ckt are  sufficient but not necessary conditions..

---

dirac's theorem is only a sufficient condition , it is not necessary condition.
It is a hamiltonian graph.

Answer 1

True it have Hamiltonian ckt