Consider a Hamiltonian Graph G with no loops or parallel edges and with |V(G)|=n≥3. Then which of the following is true?
If Dirac's condition true then Then G is hamiltonian (regarding option 1)
If Ore's condition true then Then G is hamiltonian (regarding option 3)
If condition in option 2 is correct Then G is hamiltonian (regarding option 2)
Will these three implications be true in opposite direction ??
Debasmita Bhoumik My initial comment logic was wrong. I edited my comment.
Yeas all the options are true, in fact some of this are well known theorems
if G is a simple graph of n vertices ,where n>=3 ,such that the every vertex of G has a degree at least n/2 ,is a hamiltonian circuit
if G is a simple graph of n vertices ,where n>=3 such that deg(u)+deg(v)>=n for every pair of NONADJACENT vertices u,v in the graph..then G has a Hamiltonian CKt
A vertices with no loop and paralle edges, which has atleast 1/2(n-1)(n-2)+2 edge ,is Hamiltonian
so i think all are true
@Uddipto .. ALL these are one way theorem ? in the QS they are asking in the reverse direction ?? any comment on this ?
1 is true: If G = (V, E) has n ≥ 3 vertices and every vertex has degree ≥ n/2 then G has a Hamilton circuit. proved theorem in book
2 is true. explained in comment.
3 is true: deg v + deg w ≥ n for every pair of distinct non-adjacent vertices v and w of G (*)
therefore: all are ture
Hence, option (A) is correct.
https://www.quora.com/Let-G-be-a-simple-graph-with-n-vertices-and-1-2*-n-1-n-2-+2-edges-How-do-I-use-Ores-theorem-to-prove-that-G-is-Hamiltonian# // (Good read of answer by "Amitabha Tripathi " Professor of Mathematics at IIT Delhi).
Hence, option (B) is correct.
deg v + deg w ≥ n for every pair of distinct non-adjacent vertices v and w of G, then G is Hamiltonian.
Hence, option (C) is correct.
Therefore, all options are true. Hence, Option (D) is correct.
For more explanation and validation of the above options in the question one may refer to following module of NPTEL.
Feedback for next edition (if ever there's...