adplus-dvertising
frame-decoration

Question

Consider a Hamiltonian Graph G with no loops or parallel edges and with |V(G)|=n≥3. Then which of the following is true?

a.

deg(v) ≥ n/2 for each vertex v

b.

|E(G)| ≥ 1/2(n-1)(n-2)+2

c.

deg(v)+deg(w) ≥ n whenever v and w are not connected by an edge

d.

All of the above

Answer: (d).All of the above

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Consider a Hamiltonian Graph G with no loops or parallel edges and with |V(G)|=n≥3. Then which of the following is true?

Similar Questions

Discover Related MCQs

Q. Which of the following statements is false?
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadth-first search cannot be used to find connected components of a graph.
(C) Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely.
(D) Depth-first-search can be used to find the components of a graph.

Q. Which of the following strings would match the regular expression: p+[3-5]*[xyz] ?

I. p443y
Il. p6y
III. 3xyz
IV. p35z
V. p353535x
Vl. ppp5

Q. Match the following:
List-I                  List-II
a. Absurd          i. Clearly impossible being
contrary to some evident truth.
b. Ambiguous   ii. Capable of more than one
interpretation or meaning.
c. Axiom            iii. An assertion that is accepted
and used without a proof.
d. Conjecture    iv. An opinion Preferably based
on some experience or wisdom.

Code:
     a   b   c    d

Q. The functions mapping R into R are defined as:

f(x) = x^3-4x, g(x)=1/(x^2+1) and h(x)=x^4

Then find the value of the following composite functions:
hog(x) and hogof(x)

Q. How many multiples of 6 are there between the following pairs of numbers?

0 and 100   and     -6 and 34

Q. A recursive function h, is defined as follows:

h(m) = k, if m=0
= 1, if m=1
= 2h(m-1) + 4h(m-2), if m≥2

If the value of h(4) is 88 then the value of k is:

Q. The asymptotic upper bound solution of the recurrence relation given by

T(n)= 2T(n/2)+n/log n is:

Q. The minimum number of scalar multiplication required, for parenthesization of a matrix-chain product whose sequence of dimensions for four matrices is <5,10,3,12,5> is

Q. What is the probability that a randomly selected bit string of length 10 is a palindrome?

Q. Consider a weighted complete graph G on the vertex set {v1, v2, …. vn} such that the weight of the edge (vi, vj) is 4 |i – j|. The weight of minimum cost spanning tree of G is:

Q. The symmetric difference of two sets S1 and S2 is defined as

S1ΘS2 = {x|xϵS1 or xϵS2, but x is not in both S1 and S2}

The nor of two languages is defined as
nor (L1,L2) = {w|w ∉ L1 and w|w ∉ L2}

Which of the following is correct?

Q. Consider a source with symbols A, B, C, D with probabilities 1/2, 1/4, 1/8, 1/8 respectively. What is the average number of bits per symbol for the Huffman code generated from above information?

Q. How many committees of five people can be chosen from 20 men and 12 women such that each committee contains at least three women?

Q. Which of the following is/are not true?

(a) The set of negative integers is countable.
(b) The set of integers that are multiples of 7 is countable.
(c) The set of even integers is countable.
(d) The set of real numbers between 0 and 1/2 is countable.

Q. A data cube C, has n dimensions, and each dimension has exactly p distinct values in the base cuboid. Assume that there are no concept hierarchies associated with the dimensions. What is the maximum number of cells possible in the data cube, C?

Q. Suppose that from given statistics, it is known that meningitis causes stiff neck 50% of the time, that the proportion of persons having meningitis is 1/50000, and that the proportion of people having stiff neck is 1/20. Then the percentage of people who had meningitis and complain about stiff neck is:

Q. How many solutions are there for the equation x+y+z+u=29 subject to the constraints that x≥1, y≥2, z≥3 and u≥0?

Q. Given two sequences X and Y:

X = < a, b, c, b, d, a, b >
Y = < b, d, c, a, b, a >

The longest common subsequence of X and Y is:

Q. If there are n integers to sort, each integer has d digits and each digit is in the set {1,2, ..., k}, radix sort can sort the numbers in:

Q. Consider a complete bipartite graph km,n. For which values of m and n does this, complete graph have a Hamilton circuit ?