adplus-dvertising
frame-decoration

Question

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

(i) deg(v) ≥ n/3 for each vertex v
(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge
(iii) E(G) ≥ 1/3(n−1)(n−2)+2

a.

(i) and (iii) only

b.

(ii) only

c.

(ii) and (iii) only

d.

(iii) only

Answer: (b).(ii) only

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. If a graph (G) has no loops or parallel edges, and if the number of vertices (n) in the graph is n≥3, then graph G is Hamiltonian if (i) deg(v) ≥ n/3 for each vertex v (ii)...

Similar Questions

Discover Related MCQs

Q. Consider two sequences X and Y:

X = <0,1,2,1,3,0,1>
Y = <1,3,2,0,1,0>

The length of longest common subsequence between X and Y is

Q. Consider the following terminology and match List I with List II and choose the correct answer from the code given below.

b = branching factor
d = depth of the shallowest solution
m = maximum depth of the search tree
l = depth limit

List I List II
(Algorithms) (Space Complexity)
(a) BFS search (i) O(bd)
(b) DFS search (ii) O(b^d)
(c) Depth-limited search (iii) O(bm)
(d) Iterative deepening search (iv) O(bl)

Q. Consider the following statements:

S1: A heuristic is admissible if it never overestimates the cost to reach the goal.
S2: A heuristic is monotonous if it follows triangle inequality property.

Which of the following is true referencing the above statements?

Q. Consider a vocabulary with only four propositions A, B, C and D. How many models are there for the following sentence?

¬A ∨ ¬B ∨ ¬C ∨ ¬D

Q. Consider the sentence below:

“There is a country that borders both India and Nepal”
Which of the following represents the above sentence correctly?

Q. A full joint distribution for the Toothache, Cavity and Catch is given in the table below. What is the probability of Cavity, given evidence of Toothache?

Q. E is the number of edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of Ford-Fulberson algorithm is bounded by:

Q. Which of the following statements is false about convex minimization problem?

Q. The following LPP
Maximize z = 100x1+2x2+5x3
Subject to

14x1+x2−6x3+3x4 = 7
32x1+x2−12x3 ≤ 10
3x1−x2−x3 ≤ 0
x1, x2, x3, x4 ≥ 0

has

Q. Digital data received from a sensor can fill up 0 to 32 buffers. Let the sample space be S={0, 1, 2, .........., 32} where the sample j denote that j of the buffers are full and
p(i) =1/561 (33 - i). Let A denote the event that the even number of buffers are full. Then p(A) is:

Q. The equivalence of

¬ ∃x Q(x) is:

Q. Match the following in List - I and List - II, for a function f:

List - I
(a) ∀x ∀y (f (x)=f (y) → x=y)
(b) ∀y ∃ x (f (x)=y)
(c) ∀x f (x)=k

List - II
(i) Constant
(ii) Injective
(iii) Surjective

Code:
(a) (b) (c)

Q. Which of the relations on {0, 1, 2, 3} is an equivalence relation?

Q. Which of the following is an equivalence relation on the set of all functions from Z to Z?

Q. Which of the following statements is true?

Q. If the time is now 4 O'clock, what will be the time after 101 hours from now?

Q. Let m = (313)4 and n = (322)4. Find the base 4 expansion of m + n.

Q. How many distinguishable permutations of the letters in the word BANANA are there?

Q. Let P and Q be two propositions, ⌐(P ↔ Q) is equivalent to:

Q. Negation of the proposition Ǝ x H(x) is: