The Gateway to Computer Science Excellence
+1 vote

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
in Graph Theory by Active
recategorized ago by | 1.7k views
  • 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 ??

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
What is correct answer ? any answer keys ?
edited explanation
@deka, debosmita, see my answer

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

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

3 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


so i think all are true

by Boss

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

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..
@uddipto.. plz enlight about this reverse direction issue
got it
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

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

therefore: all are ture

option 4

by Active
0 votes

      Hence, option (A) is correct.

  • Any graph with n vertices and at least $\frac{1}{2}\left ( n-1 \right )\left ( n-2 \right ) + 2$ edges must be hamiltonian.*-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.

  • Let G be a (finite and simple) graph with n ≥ 3 vertices. Degree of a vertex v ( i.e deg v ) in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if 

deg v + deg w ≥ n for every pair of distinct non-adjacent vertices v and w of G, then G is Hamiltonian.'s_theorem

    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.

by Active
edited by
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
52,218 questions
59,888 answers
118,127 users