# There exists a graph on $n$ vertices such that every vertex has degree at least $\frac{1}{2}n -1$

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?

• Hint: If $n=2m$ is even there is an easy example where every vertex has order $m-1$. – Mark Bennet Nov 25 '18 at 20:56
• I'm afraid I don't see which graph you are referring to. – Wesley Strik Nov 26 '18 at 11:32
• The one I'm thinking of is not connected. – Mark Bennet Nov 26 '18 at 12:59
• If we take two disconnected components $K_{m-1}$ and $K_{m-1}$, together they have $2m$ vertices and every vertex has degree $m-1 = \frac{1}{2}n-1$ as desired. – Wesley Strik Nov 26 '18 at 18:01
• If $n=2m+1$ we cannot provide this argument and we have to come up with something different. – Wesley Strik Nov 26 '18 at 18:02

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.