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

Question

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 ?

Answer 1

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.

Answer 2

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.

Answer 3

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