# prove that a graph with p vertices and $2+(p-1)(p-2)/2$ edges is hamiltonian

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 ?

• Do you assume the graph connected? – Patrick Da Silva Jan 2 '16 at 19:45
• @PatrickDaSilva with that many vertices, it must be connected – MCT Jan 2 '16 at 19:47
• 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. – Patrick Da Silva Jan 2 '16 at 19:51
• @patrickdasilva it is from the book called 'A first course in descrete mathemathics' written by Ian Anderson ... see this link : books.google.com/… – 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...

• 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. – 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.

• @bjcbits028 please explain it completely :) i've tried to solve this problem for two weeks ! but i could'nt :( – Arman Malekzadeh Jan 2 '16 at 19:56
• 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. – MCT Jan 2 '16 at 20:17