Theorem: Any graph with $n\geq3$ vertices and degree $\delta(G)\geq n/2$ contains a Hamiltonian cycle. My proof: Proving $G$ is connected is trivial. Let $$P=x_1 x_2 x_3 \cdots x_k$$ be the longest path in $G$. If $x_1$ is adjacent to some $v\notin P$, then path $vP$ is longer than $P$ contradicting the fact that $P$ is the longest path. Same argument holds for $x_k$. Thus all vertices forming an edge with $x_k$ and $x_1$ lie on $P$. We know that $$\operatorname{deg}(x_1)\geq n/2$$ $$\operatorname{deg}(x_k)\geq n/2$$ That means at least $n/2$ vertices from the set $S_1=\{x_2,x_3,x_4\cdots,x_k\}$ form an edge with $x_1$.
Also $n/2$ vertices from the set $S_k=\{x_1,x_2,x_3,\cdots,x_{k-1}\}$
The longest path cannot be bigger than the amount of vertices of $G$ thus $k\leq n$. Furthermore, we have $$|S_1|=|S_k|=k-1<n$$ From each of $S_1,S_k$ we have to choose exactly $n/2$ elements, thus $n$ elements from both sets. By Pigeonhole principle there exists some $x_i$, such that it is chosen from both $S_1,S_k$ thus forming an edge with both $x_1$ and $x_k$. This gives cycle $$C=x_1 x_2\cdots x_i x_k x_{k-1} x_{k-2}\cdots x_{i+1} x_i x_1$$ Now it sufficies to prove $C$ is Hamiltonian and that's the point where I am stuck. I've been given a suggestion to proceed by contradiction. Suppose we have some vertex $y\notin C$ such that it forms an edge with some $x_j$ which would give a contradiction because we would be able to construct longer path than $P$.
1.) How can I assume that $y$ forms an edge with some $x_j$?
2.) Using the vertex $y$, how do I construct the longer path than $P$ is thus contradicting the statement that $C$ is non-Hamiltonian thus proving the theorem?
Since you have shown that the graph is connected, the portion of the graph not contained in your cycle must connect to some point of your cycle. In particular, there will be at least one vertex y that satisfies your requirements. This y can be strung together with your cycle to create a path of larger length contradicting your initial assumption. More explicitly, say your cycle is $x_1, \dots, x_k$ and y connects to $x_j$, then your new path is $y, x_j, x_{j+1}, \dots, x_k, x_1, \dots, x_{j-1}$.