# 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. Commented Apr 26, 2019 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? Commented Apr 26, 2019 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. Commented Apr 26, 2019 at 15:01

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