Dark Mode

625 views

0 votes

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?

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

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

1 vote

All of the Above, this is a duplicate question

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

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

0 votes

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