0
$\begingroup$

Recently i studied three theorems which says about Hamiltonian graph, they are as follows,

  1. Dirac's Theorem: Let G be some simple graph of order n >= 3,

for all vertices of the graph G, its degree >= n/2 then we say given simple graph is actually an Hamiltonian graph.

  1. Ore's Theorem: Let G be a simple graph of order n >=3,

sum of degree of any two vertices which are not adjacent >= n then we say given simple graph is an Hamiltonian graph.

  1. Another is a simple graph with (n-1) C 2 edges + 2 edges implies its an Hamiltonian graph.

given this basic definition, my question is will this even work in reverse manner, suppose if i give an hamiltonian graph will all this theorem satisfy? Below is one question i am wondering about!!

enter image description here

thankyou in advance! :)

$\endgroup$
3
  • $\begingroup$ Will what work in reverse manner? What does it mean to "work in reverse manner"? We're not looking for posts that just have the statement of an exercise-style task and a request for us to solve it for you. What are your thoughts? What progress have you made? Have you tried working through some examples? You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Commented Oct 30, 2022 at 0:49
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. You've been given this feedback before. We require you to provide proper attribution to your sources: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Commented Oct 30, 2022 at 0:50
  • $\begingroup$ Hi @D.W. , i will take care, will use Latex next time! thankyou $\endgroup$
    – Niraj Jain
    Commented Oct 30, 2022 at 3:32

1 Answer 1

1
$\begingroup$

Consider a graph $G$ that is a single cycle of length $\geqslant 5$. Then it should be clear that none of the properties is true, while $G$ is hamiltonian.

$\endgroup$
1
  • $\begingroup$ yeah it is trivial! thanks @Nathaniel $\endgroup$
    – Niraj Jain
    Commented Oct 29, 2022 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.