Clarifying Dirac's theorem

Question

Theorem : If $G$ is a simple graph with $n$ vertices with $ n ≥ 3$ such that the degree of every vertex in G is at least $ n/2$, then $G$ has a Hamilton circuit.

In this if $n$ is odd, should I consider the greatest integer not exceeding $n/2$ or least integer greater than $n/2$?

Answer 1

Generalizing my comment, consider the complete bipartite graph $K_{n,n-1}$. This graph is not Hamiltonian since a Hamiltonian cycle would be of odd length. On the other hand, the degree of every vertex is at least $n-1$, which is the greatest integer not exceeding $\frac{2n-1}{2}$.

So to answer your question, you need to take the ceiling of $\frac{|V(G)|}{2}$.

Answer 2

Taking the greatest integer not exceeding n/2 will suffice when n is odd because the sum of degrees of any two vertices will be at least n-1 and the existence of a Hamiltonian circuit follows from Ore's Theorem