If a graph G has no loops or parallel edges and if the number of vertices(n)…
2018
If a graph G has no loops or parallel edges and if the number of vertices(n) in the graph is n≥3, then the graph G is Hamiltonian if
I. deg(v) ≥ n/3 for all vertices v
II. deg v +deg(w)≥n whenever v and w are not connected by edge
III. E(G)>=1/3(n-1)(n-2)+2
- A.
(I) and (II) only
- B.
(I) and (III) only
- C.
(III) only
- D.
(II) only
Attempted by 58 students.
Show answer & explanation
Correct answer: D
Statement I is incorrect because Dirac’s theorem requires the degree of every vertex to be at least n divided by 2. Here it is given as n divided by 3, which is weaker and does not guarantee a Hamiltonian graph.
Statement II is correct because it matches Ore’s theorem. This condition is sufficient to ensure that the graph is Hamiltonian.
Statement III is not sufficient. A graph can satisfy this edge condition and still not be Hamiltonian, for example if it has an isolated vertex.
Therefore, only Statement II is valid.
A video solution is available for this question — log in and enroll to watch it.