A Hamiltonian graph is a graph which has a Hamiltonian cycle.
A Hamiltonian cycle is a cycle which crosses all of the vertices of a graph. According to Ore's theorem , if $p \ge 3$ we have this :

For each two non-adjacent vertices $u,v$ , if $\deg(u)+\deg(v) \ge p$, then the graph is Hamiltonian.

Now suppose that we have a graph with $p$ vertices and $2+(p-1)(p-2)/2$ edges. How can we prove that this graph is Hamiltonian ?

  • $\begingroup$ Do you assume the graph connected? $\endgroup$ – Patrick Da Silva Jan 2 '16 at 19:45
  • $\begingroup$ @PatrickDaSilva with that many vertices, it must be connected $\endgroup$ – MCT Jan 2 '16 at 19:47
  • $\begingroup$ Bleh. I am very tired. Sorry! For some reason I associated $2^p$ to the number of edges of the complete graph. Don't ask why. $\endgroup$ – Patrick Da Silva Jan 2 '16 at 19:51
  • 1
    $\begingroup$ @patrickdasilva it is from the book called 'A first course in descrete mathemathics' written by Ian Anderson ... see this link : books.google.com/… $\endgroup$ – Arman Malekzadeh Jan 2 '16 at 19:52

Suppose there were two non-adjacent vertices with $\deg(u) + \deg(v) < p$.

Then delete those two vertices and all edges connected to them. (the number of edges deleted is at most $p-1$)

We are left with a graph with $p-2$ vertices and at least $2 + (p-1)(p-4)/2$ edges, which is one more than $(p-2)(p-3)/2$, the latter being the most edges that a graph with $p-2$ vertices can have. Thus, we get a contradiction.


I think you can begin by considering a graph, say X, with p-1 vertices, this fetches you a complete graph with (p-1)(p-2)/2 vertices then if you add another vertex {(p-1)+1=p} you are in essence, connecting one extra node any other two nodes.

Now you know that a complete graph, X is Hamiltonian because it is complete and to this cycle C* you add two more edges and a node to get a bigger Cycle C.

Maybe this should work...

  • $\begingroup$ I don't think this works since it assumes that the structure of any graph with $p$ vertices and $(p-1)(p-2)/2 + 2$ edges is that of $K^{p-1}$ with two edges connected to some other node. $\endgroup$ – MCT Jan 2 '16 at 20:03

I think you may apply Dirac's theorem on hamiltonian cycle (Dirac theorem).

Let us assume that the degree of each vertex is less than p/2. So, by using degree-edges theorem

maximum (|E|) = 1/2 * (p * (p/2)) = p*p/4.

But according to your question number of edges are (p-1) * (p-2)/2 + 2 which is greater than p * p/4. This proves that on average the degree of each vertex is greater than p/2. So by applying Dirac's theorem, the graph is Hamiltonian.

  • $\begingroup$ @bjcbits028 please explain it completely :) i've tried to solve this problem for two weeks ! but i could'nt :( $\endgroup$ – Arman Malekzadeh Jan 2 '16 at 19:56
  • $\begingroup$ No your proof is not right. The contradiction is that THERE EXISTS a vertex with degree less than $p/2$, not that every edge is as such. Using the correct contradictory statement, you cannot prove anything. $\endgroup$ – MCT Jan 2 '16 at 20:17

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.