A graph G with number of vertices greater and equal than three i.e. (n ≥ 3) is a Hamiltonian graph, if the degree of each vertex is greater and equal to . . . .

1. AEqual to number of vertices
2. BDouble of number of vertices
3. CHalf of number of vertices
4. DFour times of number of vertices

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. Half of number of vertices

Explanation

Dirac's theorem: a simple graph with n ≥ 3 vertices in which every vertex has degree at least n/2 is Hamiltonian.