Refinement of Dirac's theorem on Hamiltonian graphs

Question

Dirac's theorem states that if degree of each vertex of a graph $G=(V,E)$ is not less than $|V|/2$, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I do not know the reference other than competition problem) that if all degrees are exactly $(|V|-1)/2$, the graph still have Hamiltonian cycle. So the question.

Let $G$ be a graph with $2n+1$ vertices and all degrees at least $n$ but without Hamiltonian cycle. What is minimal possible number of edges in $G$? There are two examples with $n(n+1)$ edges: $K_{n,n+1}$ and two $K_{n+1}$'s glued by a vertex. Maybe, this is least possible actually?

UPDATE. It looks that what actually is proved in the result to which I refer is that the graph on $2n+1$ vertices without Hamiltonian cycle and all degrees at least $n$ either contains $K_{n,n+1}$ or coincides with two $K_{n+1}$'s glued by a vertex. This answers the question, if anybody is interested I may leave a proof here, if not, just remove the question.

Answer 1

Let $G$ be a graph with $2n+1$ vertices and all degrees at least $n$ but without Hamiltonian cycle. Consider two cases.

1) There is a cycle $C=x_1\dots x_{2n}x_1$ of length $2n$. Let $y$ be the vertex not in this cycle. If it is joined with two consecutive vertices in $C$, then we have a Hamiltonian cycle. Thus $y$ is joined, say, with $x_1,x_3,\dots,x_{2n-1}$. Replace $C$ to a new cycle, replacing fragment $x_{2k-1}x_{2k}x_{2k+1}$ to $x_{2k-1}yx_{2k+1}$. Apply the same argument, now $x_{2k}$ plays role of $y$. We see that $x_{2k}$ must be joined with $x_{2i-1}$ for all possible indices $2i-1,2k$. It follows that $G$ contains $K_{n,n+1}$ ($x_1,x_3,\dots,x_{2n-1}$ is first part and $y,x_2,x_4,\dots,x_{2n}$ the second part. It may contain also arbitrary set of edges between vertices of the first part.

2) There is no such a cycle. Consider Hamiltonian path $P=x_1\dots x_{2n+1}$ in $G$. Then $x_1$ is joined with some (at least) $n$ vertices in $P$. If $x_1$ is joined with $x_k$, then $x_{2n+1}$ can not be joined with $x_{k-1}$, nor with $x_{k-2}$. If for some $k$ it appears that $x_1$ is joined with $x_k$, $k>2$, but not with $x_{k-1}$, we get already $n+1$ forbidden vertices for $x_{2n+1}$. Thus $x_1$ must be joined with $x_2,\dots,x_{n+1}$ and $x_{2n+1}$ with $x_{n+1},\dots,x_{2n}$. Now for any $k=2,\dots,n$ change path to $x_kx_{k-1}\dots x_1x_{k+1}\dots x_{2n+1}$. Repeat the same argument. We see that $x_1,\dots,x_{n+1}$ form a clique, as well as $x_{n+1},\dots,x_{2n+1}$. Thus $G$ coincides with two cliques of size $n+1$ glued by their common vertex. Adding any edge produces a Hamiltonian cycle.