UGC NET CSE | January 2017 | Part 2 | Question: 5

Question

Consider a Hamiltonian Graph $G$ with no loops or parallel edges and with $\left | V\left ( G \right ) \right |= n\geq 3$. The which of the following is true?

• A. $\text{deg}\left ( v \right )\geq \frac{n}{2}$ for each vertex $v\\$
• B. $\left | E\left ( G \right ) \right |\geq \frac{1}{2}\left ( n-1 \right )\left ( n-2 \right )+2 \\$
• C. $\text{deg}\left ( v \right )+\text{deg}\left ( w \right )\geq n$ whenever $v$ and $w$ are not connected by an edge
• D. All of the above

Comments

@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

Answer 1

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

Comments

@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

Answer 2

All of the Above, this is a duplicate question

Check here for explanation https://gateoverflow.in/115602/ugcnet-dec2016-ii-5

Answer 3

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

Answer 4

• A sufficient (but by no means necessary) condition for a simple graph 'G' to have a hamiltonian circuit is that the degree of every vertex in 'G' be at least $\frac{n}{2}$ where 'n' is the number of vertices in 'G'. https://www.sas.upenn.edu/~htowsner/uconnprev/math340f13/Lecture%207%20(Sep%2019).pdf

      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.

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.

• 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.       

 https://en.wikipedia.org/wiki/Ore'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.

https://nptel.ac.in/courses/111106050/Module6.pdf