# Dirac's theorem question

Give an example to show that the condition $\deg(v) \geq n/2$ in the statement of Dirac's theorem cannot be replaced by $\deg(v) \geq (n-1)/2$

The textbook gives the solution: The complete bipartite graph $K_{n/2 - 1, n/2 + 1}$ if $n$ is even, and $K_{(n-1)/2, (n+1)/2}$ if $n$ is odd.

If anyone can explain this more thoroughly it would be greatly appreciated, thanks!

-
The complete bipartite graph $K_{(n-1)/2, ~ (n+1)/2}$ has $(n-1)/2 + (n+1)/2 = n$ vertices.
Each vertex has degree greater than or equal to $(n-1)/2$ but this graph does not contain any Hamiltonian cycles, so the conclusion of Dirac's theorem does not hold.
You may wish to consider, for example, $K_{1,2}$ or $K_{2,3}$.