# Hamiltonian Cycle with n vertex graph

Let a n-vertex graph such that every pair of not adjacent vertices a & b has degree(x) + degree(y) $$\geq$$ n. Show the graph contains a Hamiltonian cycle.

By dirac's thm, a simple graph with n vertices (n ≥ 3) is Hamiltonian if every vertex has degree n / 2 or greater. How would i relate this thm to the question?

• Try to mimic the proof of Dirac's theorem using the given weaker degree condition. The key point is finding a vertex in the middle of the longest path that both end points are adjacent to. – Jeremy Dover Apr 26 '19 at 13:50
• how do i sub the new conidition to the proof of dirac in the step of finding vertex j in the longest path? – james black Apr 26 '19 at 14:51
• That is the crux of the problem. See how the condition $deg(v) \ge \frac{n}{2}$ is used in the proof of Dirac's theorem to ensure two sets of vertices intersect, and try to extend it to the weaker condition in the problem. – Jeremy Dover Apr 26 '19 at 15:01

I guess non-adjacent vertices should be named $$x$$ and $$y$$. Then you ask to prove Ore’s theorem.