A graph G with n ≥ 3 vertices is a Hamiltonian graph if the degree of each vertex is greater than or equal to
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. half the number of vertices
Explanation
Dirac's theorem: a simple graph with n ≥ 3 vertices in which every vertex has degree ≥ n/2 is Hamiltonian.More Discrete Structures and Optimization questions
- A coin is tossed successively three times. For the event E of getting exactly one head or exactly two heads, with sample space S (n denotes…
- Consider the following, where p and q are two statements. (A) ~(p ∧ q) ≡ ~p ∨ ~q (B) ~(p ∨ q) ≡ ~p ∧ ~q (C) p ∧ ~p ≡ T (D) ~(p ⇒ q) ≡ p ∧ ~…
- Let L(x, y) be the statement "x loves y", where the domain for both x and y consists of all people in the world. Use quantifiers to express…
- Match List I (Queries) with List II (Probability)List I List II (A) A bag contains 6 white and 4 red balls. Two balls are drawn at random.…
- Let G(V, E) be an undirected graph with l edges. Then the sum of the degrees of all vertices is equal to
- 40 software professionals were interviewed for a job. 25 knew PYTHON, 20 knew JAVA and 7 knew neither language. How many knew both language…