Show that there are non-Hamiltonian graphs of any even order $p ≥ 4$ satisfying $δ(G) = p/2 − 1$ and that there are non-Hamiltonian graphs of any odd order $p ≥ 3$ satisfying $δ(G) = \frac{p − 1}2$.
Can't we just take $K(\frac{p}2-1,\frac{p}2+1)$ for the first ones and $K(\frac{p − 1}2, \frac{p + 1}2)$ for the second part since bipartite complete graphs $K(m,n)$ are not Hamiltonian when $n\neq m$ ?
I always see over complicated answers like $K_1 + (K_{(p−1)/2} ∪ K_{(p−1)/2})$
Your answer is correct, nice examples! Let $U=[m]\times\{1\}$ be the vertex set with fewer vertices, and $V=[n]\times\{2\}$ the other vertex set. For even $p$ we notice that $\delta(G)=\frac{p}{2}-1=m$ and $\Delta(G)=\frac{p}{2}+1=n=m+2$ are the only degrees, attained on $V$ and $U$ respectively. Assume a hamiltonian cycles exists. Due to the symmetries of the complete bipartite graph all vertices in $U$ are exchangeable, and the same goes for $V$. Hence, we should obtain a Hamiltonian cycle by choosing the edges $\{(1,1),(1,2)\},\dots\{(m,1),(m,2)\},\{(1,2),(2,1)\},\dots,\{(m-1,2),(m,1)\}$, but now we're stuck at $(m,2)$, because $(m+1,2)$ $(n,2)$ are still open, but we can only move to $U$ where all vertices have already been visited.
The idea for $p$ odd is the same, with degrees $\delta(G)=\frac{p-1}{2}=m$ on $V$ and $\Delta(G)=\frac{p+1}{2}=n=m+1$ on $U$. Proceeding as before, we're stuck at $(m,2)$ because $(n,2)$ is still open, but all vertices in $U$ have already been visited.