Question

If G is a simple graph with n-vertices and n>=3, the condition for G has a Hamiltonian circuit is __________

(a) the degree of each vertex is at most n/2

(b) the degree of each vertex is equal to n

(c) the degree of every vertex is at least n+1/2

(d) the degree of every vertex in G is at least n/2

I have been asked this question in class test.

The above asked question is from Trees topic in chapter Trees of Discrete Mathematics

Answer 1

The correct option is (d) the degree of every vertex in G is at least n/2

The best explanation: A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit. If there is a vertex of degree one in a graph then it is impossible for it to have a Hamiltonian circuit. If G is a simple graph with n-vertices and n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.