Prove that $\Delta(G)\le \frac{n-1}{2}$

Question

I have to prove that if graph $G$ is not Hamiltonian, but $G-v$ is Hamiltonian for every $v\in V(G)$ then $\Delta(G)\le \frac{n-1}{2}$. I tried to prove this with contradiction. So, first if we assume that $\Delta(G)\ge \frac{n+1}{2}$, and let $v$ be vertex with maximum degree. Then, we remove at least $\frac{n}{2}+1$ edges from G. But not sure how to come into contradiction, how to prove that G-v is Hamiltonian?

Answer 1

It's very easy. Let $\operatorname{deg}(v)>(n-1)/2$.

Since the graph $G-v$ is Hamiltonian, all its $n-1$ vertices lie on a Hamiltonian cycle.

Since $\operatorname{deg}(v)>(n-1)/2$ then there are two neighbor vertices $u_1$ and $u_2$ on this cycle adjacent to $v$.

But then we can construct a Hamiltonian cycle of graph $G$ by adding such a path $\ldots u_1vu_2\ldots$.

We obtained a contradiction.