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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Srivatsan Dec 16 '11 at 9:33
  • $\begingroup$ 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? $\endgroup$ – Pavel Dec 16 '11 at 9:45
  • 2
    $\begingroup$ [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. $\endgroup$ – Srivatsan Dec 16 '11 at 9:45
  • $\begingroup$ 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. $\endgroup$ – Pavel Dec 20 '11 at 16:07
  • $\begingroup$ 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. $\endgroup$ – bof Aug 28 '17 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}$ .

  • $\begingroup$ 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. $\endgroup$ – user21436 Mar 23 '12 at 4:59

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.

  • $\begingroup$ 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. $\endgroup$ – Pavel Dec 20 '11 at 16:34
  • $\begingroup$ 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." $\endgroup$ – Paul Dec 20 '11 at 22:33
  • $\begingroup$ Well, thanks anyway, I still appreciate your answer. $\endgroup$ – Pavel Dec 21 '11 at 8:19
  • $\begingroup$ The link doesn't work. $\endgroup$ – user 170039 Dec 4 '18 at 15:45

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 .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.