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.
if $G$ has a vertex of degree two or three then by removing it you get a graph on $7$ vertices with at least 19 edges which is at most $2$ edges short from being complete. Then
a hamiltonian path could be found in the new graph between two of the neighbours of the deleted vertex which with the deleted vertex will give you a hamiltonian cycle in the original graph.
Best Answer
This is a very famous theorem due to Dirac. I will sketch the proof here. You can easily find more detailed proofs online.
Theorem (Dirac): Let $G(V,\ E)$ be a simple graph of order $|V|\ge 3$. If each vertex $v\in V$ satisfies $\deg v \ge \frac{n}{2}$ then $G$ is Hamiltonian.
Proof Sketch: First note that the degree condition implies that $G$ is necessarily connected. Now let $$P = (v_1,\ \cdots,\ v_k)$$ denote the longest path in $G$. Necessarily, every neighbor of the end points $v_k$ and $v_1$ are contained in $P$ and that each must be connected to $\frac{n}{2}$ vertices in the path.
Since the two vertices total at least $n$ edges to the path, there must be an index $i$ such that $(v_1,\ v_{i+1})\in E$ and $(v_{i},\ v_k)\in E$. The claim is that $$C = (v_1,\ v_{i+1},\ \cdots,\ v_k,\ v_i,\ \cdots,\ v_1)$$ is a Hamiltonian cycle. If there were vertices excluded from this cycle, then pick any vertex connected to $P$ but not in $P$, say $x\notin P$ and $(x,\ v_j)\in E$. But then we can extend $P$ by starting at $x$ and cycling through $C$. This contradicts the fact that $P$ is the longest path in $G$. Therefore $G$ is Hamiltonian. $\square$