+1 vote
950 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 | 950 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

+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

so i think all are true

answered by Boss (18.5k 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
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

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)

+1 vote