recategorized
1,982 views
0 votes
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?

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

4 Answers

1 votes
1 votes

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

0 votes
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
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.

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

edited by
Answer:

Related questions

0 votes
0 votes
4 answers
2
go_editor asked Mar 24, 2020
992 views
Match the following :$\begin{array}{llll} & \textbf{List – I} & {} & \textbf{List – II} \\ \text{a.} & \text{Absurd} & \text{i.} & \text{Clearly impossible being con...
0 votes
0 votes
2 answers
4
go_editor asked Mar 24, 2020
875 views
How many multiples of $6$ are there between the following pairs of numbers?$0$ and $100$ and $-6$ and $34$$1$ and $6$$17$ and $6$$17$ and $7$$16$ and $7$