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
1 question paper link