Maximum number of edges in a non-Hamiltonian graph

I need to show that the maximum number of edges of non-Hamiltonian, simple graph, on $n$ vertices noted by $t(n,H_n)$ is $\binom{n-1}{2} + 1$. It's essential to show the upper and lower bounds for this question.

Now, I can see why I need to show the upper bound - for $t(n,H_n) > \binom{n-1}{2} + 1$ there's a clique on $n-1$ vertices and one other vertex with at least 2 edges. Surely, a Hamiltonian cycle exist in such graph.

What about the lower bound, though? Am I need to prove that for every $t(n,H_n) \leq \binom{n-1}{2} + 1$ there is no Hamiltonian cycle? By negation, I seem to not advance anywhere, because I don't know of any necessary conditions for a Hamiltonian cycle to exist, beside the cut-vertex one. Can someone give me a clue on that?

Thanks in advance.

Solution 1:

Found a lot easier proof for the harder part, using Ore's theorem: If $G$ is complete, there's a Hamiltonian cycle. So suppose it's not. We'll take some non-neighbor vertices $v,w$, and delete them from the graph. For the resulting graph $G'$ - $|E(G')| \geq \binom {n-1}{2} + 2 - (d(v)+d(w))$. In the complete graph on $n-2$ vertices there are $\binom {n-2}{2}$ edges. So, lastly, we get that $$\binom{n-2}{2} \geq \binom{n-1}{2} + 2 - (d(v)+d(w))$$ and after some easy operations, we get that $$d(v)+d(w) \geq n$$ which is exactly Ore's condition for a Hamiltonian graph to exist.

Solution 2:

A different induction solution:

Induction hypotheses: A (simple) graph G with $\binom {n-1} 2 +2 $ edges has a hamiltonian cycle.

For $n=2$ and $n=3$, we can prove the claim by exhausting all possibilities(where $n$ is the number of vertices).

For $n>3$: There is a vertex with degree atleast $n-2$. This is true because there are $\dfrac{(n-1)(n-2)}2+2$ edges, hence sum of degree of all the vertices is $(n-1)(n-2)+4=n^2-3n+6$. Suppose, all vertices had degree $n-3$ or less, then it would make upto a maximum of $n(n-3)$.

Case $1$: There is a vertex of degree $n-1$

Removing this vertex creates a $n-1$ vertex graph with $\dfrac{(n^2-5n+8)} 2$ edges, whereas we need $\dfrac {(n-2)(n-3)}2+2=\dfrac{(n^2-5n+10)}2$ for a hamiltonian cycle. But it is enough for a hamiltonian path to exist (from induction). Since, the removed vertex has degree $n-1$, the hamiltonian path in the smaller graph can be converted into a hamiltonian cycle in the bigger graph.

Case $2$: There is a vertex with $n-2$ and no vertex with degree $n-1$.

Removal of this vertex creates a graph with $\dfrac{(n^2-3n+2)}2-(n-2)+2=\dfrac{(n-2)(n-3)}2 +2$. By induction, the smaller graph contains a hamiltonian cycle. Since, the removed vertex has degree $n-2$, we can find two adjacent vertices in the hamiltonian cycle and insert the vertex there.(this is why we required the induction base case for $n=3$) $\blacksquare$

Example of a(is it the only?) graph with $\binom {n-1} 2+1$ edges and not hamiltonian: Union of $K_{n-1}$ and a vertex outside that shares an edge with exactly one vertex of $K_{n-1}$ .