Maximum number of edges in a non-Hamiltonian graph

Question

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.

Answer 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.

Answer 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}$ .

Answer 3

This is essentially Corollary 4.6 in the book "Graph Theory with applications" by J.A. Bondy and U.S.R. Murty, which is available here. I wonder if there is an easy proof for this statement. Maybe there is one but I don't know it. Since you said that this is a homework problem, I think you may be able to apply some theorem you have learned in your class. If you have learned Chvatal's theorem in your class (see Theorem 4.6 of the book mentioned above), which says that:

If $G$ is a non-Hamiltonian simple graph with $n\geq 3$ vertices, then $G$ is degree-majorised by some $C_{m,n}:=K_m\vee(K_m^c+K_{n-2m})$

then you can derive the required result easily as follows, as shown in the book: $$|E(G)|\leq |E(C_{m,n})|=\frac{1}{2}\Big[m^2+(n-2m)(n-m-1)+m(n-1)\Big]\leq{n-1\choose 2}+1.$$ On the other hand, you can characterize $G$ when the equality holds.

Answer 4

First see that you can have a complete graph on n-1 vertices where the number of edges is n-1 C 2 and then you just need to consider how many edges you can add to a new incoming vertex such that the resulting graph is Non- Hamiltonian. Hamiltonicity of the complete graph implies that only one edge can be added .