Hamiltonian Cycle with n vertex graph

264 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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