# 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?

• You need to show two things: (1.) If $H$ contains at least $\binom{n-1}{2} + 2$ edges, then $H$ contains a Hamilton cycle. This is the harder part. (2.) There exists a graph $H$ that contains $\binom{n-1}{2}+1$ edges and yet does not contain a Hamilton cycle. This part is easy. Commented Dec 16, 2011 at 9:33
• Thanks, it seems like a more appropriate way to look at the question. Why, though, my way is wrong? Or it just doesn't lead anywhere? Commented Dec 16, 2011 at 9:45
• [contd] You need not show that every graph with $\binom{n-1}{2}+1$ edges contains no Hamilton cycle. In fact, this is clearly false; the cycle graph on $n$ vertices is a counterexample. Commented Dec 16, 2011 at 9:45
• Not sure if someone will still read this; totally forgot that I asked it here. In (1) I've come down to the fact that if there's a vertex $v$ such that $d(v)=n-2$, I can use induction and then connect it to existing Hamiltonian cycle to get bigger cycle. Not sure how to prove that such vertex indeed exist. At most I can show there exist a vertex of degree $\geq n-2$, which doesn't help me going back in induction, when I delete it. Commented Dec 20, 2011 at 16:07
• How do you justify your claim that "for $t(n,H_n)\gt\binom{n-1}2+1$ there's a clique on $n-1$ vertices"? This doesn't seem right to me. Suppose $n=5.$ then $\binom{n-1}2+1=7 ,$ but I can draw a graph with $5$ vertices and $8$ edges which does not contain a clique on $4$ vertices. Namely, take the complete graph $K_5$ and remove two independent edges.
– bof
Commented Aug 28, 2017 at 6:51

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.

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

• I make no remark about the correctness of the answers. As for formatting, click on the time stamp above my name to access the edits. Welcome to MSE. I have upvoted your answer.
– user21436
Commented Mar 23, 2012 at 4:59
• For Case 1, why is enough for a Hamiltonian cycle to exist on the graph where the vertex with degree $n-1$ is removed? Isn't the number of edges $\frac{n^2 -5n +8}{2}$ less than the threshold $\frac{n^2 -5n +10}{2}$ set by the inductive hypothesis? What conditions will ensure that the graph on $n-1$ vertices will imply that a Hamiltonian cycle on the $n-1$ vertices exist? Commented Oct 25, 2023 at 9:30

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.

• Sorry, it seems not to be the way. The theorems mentioned in class were only Dirac, Ore and Chvatal-Erdös. Neither one seem to be of help here. Commented Dec 20, 2011 at 16:34
• That's why I said, "I wonder if there is an easy proof for this statement. Maybe there is one but I don't know it."
– Paul
Commented Dec 20, 2011 at 22:33
• Well, thanks anyway, I still appreciate your answer. Commented Dec 21, 2011 at 8:19