# Hamiltonian path exists if each two nonadjacent vertices has sum of degrees equal to n-1

Here is a question from a textbook I’m reading,

prove that a simple graph with n vertices has a hamiltonian path if the sum of degree number of each two none adjacent vertices is n-1.

I know A graph with n vertices (where n > 3) is Hamiltonian if the sum of the degrees of every pair of non-adjacent vertices is n or greater.

I know Dirac's theorem for Hamiltonian graphs tells us that if a graph of order n greater than or equal to 3 has a minimum degree greater than or equal to half of n, then the graph is Hamiltonian

How can we use them to achieve the proper answer ? A hint or an answer would be appreciated.

Thank you in advance.

• Do you know Ore's theorem? May 19, 2020 at 6:16
• @saulspatz I know both ore and Dirac theorem May 19, 2020 at 6:17
• It's a simple consequence of Ore's theorem. May 19, 2020 at 6:17

## 1 Answer

HINT

Add a new vertex $$\omega$$ to the graph, where $$\omega$$ is adjacent to each vertex of the original graph.