I have to learn the proof: if G is a graph of order p and size q, if q = ((p-1) choose 2) + 2 then G is Hamiltonian. But I'm confused... Ok they say there are 2 cases: - G isomorphic to Kn (in which case Hamiltonian) - G is not isomorphic to Kn in which case... Let uv not be an edge in G. And let H = G - {u, v} then order of H is p - 2 and q(H) = ((p-1)C2+2)-((p-2)C2) where did ((p-1)C2 + 2) come from?

Question

I have to learn the proof: if G is a graph of order p and size q, if q >= ((p-1) choose 2)  + 2 then G is Hamiltonian. But I'm confused...

Ok they say there are 2 cases:
- G isomorphic to Kn (in which case Hamiltonian)
- G is not isomorphic to Kn in which case...

Let uv not be an edge in G. And let H = G - {u, v} then order of H is p - 2 and q(H) <= (p-2)C2 where q(X) represents the size of the subgraph X.

But q(G) = q(H) + deg u + deg v (as u, v not adjacent)
Then

deg u + deg v = q(G) - q(H)
deg u + deg v >= ((p-1)C2+2)-((p-2)C2)
where did ((p-1)C2 + 2) come from?