UGC NET CSE | December 2018 | Part 2 | Question: 20

Question

If a graph (G) has no loops or parallel edges, and if the number of vertices (n) the graph is $n \geq 3$, then graph G is Hamiltonian if

1. $\text{deg(v)} \geq \frac{n}{3} \text{ for each vertex v}$
2. $\text{deg(v)} + \text{deg(w)} \geq n \text{ whenever v and w are not connected by an edge}$
3. $E(G) \geq \frac{1}{3} (n-1)(n-2)+2$

Choose the correct answer from the code given below:

• A. (i) and (iii) only
• B. (ii) only
• C. (ii) and (iii) only
• D. (iii) only

Answer 1

$deg(v)\geq \frac{n}{2}$, then the graph is Hamiltonian.This is Dirac's Theorem

$1)\,deg(v)\geq \frac{n}{3}$.So, this is false.

 

$deg(v)+deg(w)\geq n$, This is Ore's Theorem

So, $(2)$ is true

 

The maximum number of edges for a graph to be non-hamiltonian is  ${}^{n-1}C_2+1$. For proof refer this

The $(3)$ option says, $E(G)\geq \frac{1}{3}(n-1)(n-2)+2$

For $n=4$, 

${}^{4-1}C_2+1=3+1=4$. So, if the number of edges is $\leq4$, then the graph can be non-hamiltonian

$E(G)\geq \frac{1}{3}(4-1)(4-2)+2\geq 4$, this says for $E(G)\geq4$ the graph should be hamiltonian, but for $E(G)=4$ the graph can be non-hamiltonian.

So, $(3)$ should be false.

So, $(B)$ should be the answer,

Correct me if I'm wrong.