Show that for every $n \geq 1$ there exists a graph on $n$ vertices such that every
vertex has degree at least $\frac{1}{2}n -1$ and G is not Hamiltonian.
I know that Dirac's theorem implies every graph with more than $2$ vertices where every vertex has at least degree $\frac{1}{2}n$ is Hamiltonian. However, now we are asked to simply lower the degree and then show that there must always exist a counterexample to this theorem (so really the $\frac{n}{2}$ is strict).
I think induction on $n$ is a good way to approach this. By definition $K_1$ is Hamiltonian, so we cannot use this as a base case.
$n=2$, we know that the simple graph $K_2$ does not contain a Hamiltonian cycle, as it only goes from one vertex to the other. We also notice that the degree of each vertex is $1> \frac{1}{2} \cdot 2-1 =1-1=0$. Our theorem holds.
We suppose that for some graph on $k$ vertices we have that the degree of each vertex is at least $\frac{1}{2} \cdot k-1 $ and it is not Hamiltonian.
This is the most difficult part of course, the inductive step $\dots$ how do I form a graph with the same properties, maybe induction is not the way to go, what are your thoughts?
Best Answer
This question asks for an existence proof, we will consider two cases and will give a specific construction that holds for all such $n$
Let $n$ be even, then $n=2m$ for some $m \in \mathbb{Z}$. Now consider the two complete, yet disconnected graphs $K_{m}$ and $K_{m}$, each the complete graph on $m$ vertices. Their union contains $m+m=2m$ vertices. Also notice that the degree of every single vertex is $d=m-1= \frac{1}{2}n-1.$ So every vertex has the desired degree.
Let $n$ be odd, then $n=2m+1$ for some $m \in \mathbb{Z}$. Clearly this holds for the single vertex, since then we have that the degree is $0> \frac{1}{2} \cdot 1 -1 =- \frac{1}{2}.$ We will construct a new example. Consider the two complete graphs $K_{m}$ and $K_{m}$ as before, and then add a new vertex that we connect to all other vertices. This new vertex then has degree $2m=n-1 > \frac{1}{2}n -1$ and it is also a cut vertex. If it is removed, we have two disconnected components again. Every other vertex now has degree $m+1=(\frac{1}{2}n-\frac{1}{2})+1= \frac{1}{2}n + \frac{1}{2}>\frac{1}{2}n -1$. We have therefore shown that this new graph has the right degree, all that remains is to show it cannot be Hamiltonian.
If the graph would be Hamiltonian, there must exist a circuit that visits every vertex once. A circuit begins and starts at the same vertex, without loss of generality we can start at some vertex in our left graph. We start our circuit, at some point we need to use the vertex that connects the two graphs to end up in the right graph. At this moment we are stuck, we cannot go back to our original graph to finish the circuit, because then we would visit the same vertex twice, which contradicts it being a circuit. We realise that any cut graph (a graph that can be disconnected by cutting a vertex) cannot be Hamiltonian and therefore our constructed graph cannot be Hamiltonian.