The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
971 views

Consider a Hamiltonian Graph G with no loops or parallel edges and with |V(G)|=n≥3. Then which of the following is true?

  1. deg(v) ≥ n/2 for each vertex v
  2. |E(G)| ≥ 1/2(n-1)(n-2)+2
  3. deg(v)+deg(w) ≥ n whenever v and w are not connected by an edge
  4. All of the above
asked in CBSE/UGC NET by Active (3.9k points) | 971 views
+1
  • Option $2$ explanation.
  • A Two-component graph with $n$ vertices can have a maximum of $(n-1)(n-2)/2$ edges.
  • In this case, one component if complete subgraph and other one is an isolated vertex.
  • Add two more edges to join the isolated vertex to the complete subgraph.
  • We have one Hamiltonian cycles in this new graph 

 

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 ??

0
i got 4 though :(

unofficial ans keys(published by some sites) says its 4.

my logic is..

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.
 

i have not checked 3..

so gave 4..all of them
0
What is correct answer ? any answer keys ?
0
edited explanation
+1
@deka, debosmita, see my answer
0

Debasmita Bhoumik  My initial comment logic was wrong. I edited my comment. 

0
take n=4   a square graph . does condition 2 holds here

E(G)=4  , n=4  so 3x2 /2 +2 =5

so E(G) is not greater than or equal to 5

so 2 is not true

2 Answers

+1 vote

Yeas all the options are true, in fact some of this are well known theorems

Dirac's Theorem:

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

Ore's Theorem:

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

Another theorem:

A vertices with no loop and paralle edges, which has atleast 1/2(n-1)(n-2)+2 edge ,is Hamiltonian

refer:http://mathonline.wikidot.com/dirac-s-and-ore-s-theorem

so i think all are true

answered by Boss (18.6k points)
+1

@Uddipto .. ALL these are one way theorem ? in the QS they are asking in the reverse direction ?? any comment on this ?

+2
Yes! i also thought that, this is one way, but i think there is never some proper emphasis on the opposite way..

i mean if  this this satisfies, it has to be a Hamiltonian..Now if it is hamiltonian, there is not a case , where any one of the three will always occur and others may occur..
+1
@uddipto.. plz enlight about this reverse direction issue
0
got it
0
Question is given it is hamiltonian graph, your theorems are given this it is hamiltonian. So all hamiltonian graph need not satisfy this need not
0 votes

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
http://www.sas.upenn.edu/~htowsner/uconnprev/math340f13/Lecture%207%20(Sep%2019).pdf


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 (*)

https://en.wikipedia.org/wiki/Ore's_theorem

therefore: all are ture

option 4

answered by Active (3.9k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,782 questions
46,784 answers
140,761 comments
58,697 users